[DP] BOJ 1149 번 문제 풀이

문제 분석 

 

문제는 RGB 거리에 R,G,B 의 색으로 집을 칠하는 최소비용을 

구하는 것이다. 

이때, 이웃하는 집의 색은 달라야 한다.

 

예를 들어

 

G 의 인덱스가 i 라고 할 때

i + 1 과 i - 1 이 이웃하는 집이다.

 

우선 최소비용과 색을 포함할 수 있는 배열을 선언하자.

 

d[i][0] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 빨간색

d[i][1] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 초록색

d[i][2] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 파란색

 

이제 배열이 선언됐으니 점화식을 끌어내 보자.

우선 경우의 수가 하나밖에 없는 초깃값들을 초기화 하자.

 

d[0][0] = s[0][0] , d[0][1] = s[0][1] , d[0][2] = s[0][2]

 

두 번째 집은 무조건 이전 집의 색을 사용할 수 없다.

따라서 

 

d[1][0] = min( d[0][1] , d[0][2] ) + s[1][0]

 

이처럼 현재 집의 색을 제외한 

두 가지 색 중 저렴한 것을 택한다.

 

역시 초록과 파란색인 경우도 따져봐야 한다.

 

결과적으로 점화식은 

 

d[i][0] = min( d[i-1][1] , d[i-1][2] ) + s[i][0]

 

될 것이고 결괏값은

 

cout << min( min( d[n-1][0], d[n-1][1] ), d[n-1][2] )

 

min은 두 개의 인수를 받는 함수이므로 

두 번 사용해서 3개를 비교한다.

 

코드

#include "bits/stdc++.h"

using namespace std;

int d[1000][3];
int n;
int s[1000][3];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i][0] >> s[i][1] >> s[i][2];
	}

	d[0][0] = s[0][0];
	d[0][1] = s[0][1];
	d[0][2] = s[0][2];
	for (int i = 1; i <= n; i++)
	{
		d[i][0] = min(d[i - 1][1], d[i - 1][2])+ s[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2])+ s[i][1];
		d[i][2] = min(d[i - 1][1], d[i - 1][0])+ s[i][2];
	}

	cout << min(min(d[n - 1][0], d[n - 1][1]), d[n - 1][2]);

}