백준 1149 RGB거리

동적 프로그래밍을 이용해 해결할 수 있는 문제입니다. 

이 문제에서 제가 틀렸던 부분은 무조건 최소만을 생각하여 문제를 푸는 방식이였습니다. 

0을 R, 1을 G, 2를 B라고 하겠습니다.

제가 틀렸던 부분은 다음의 표의 상황입니다. 

	home[i][0]	home[i][1]	home[i][2]
i=1	1	1000	2000
i=2	1	2000	1000
i=3	2000	1000	1

만약 단순 최소값만을 이용하면 답은 1+1000+1000 이 됩니다. 

저희가 원하는 정답은 1000+1+1 이므로 최소값만을 고려하면 문제를 해결할 수 없습니다. 

이 문제는 모든 경우를 다 생각해 값을 구해놓고 그 중 최소를 찾는 문제입니다. 

문제에서 주어진 예시를 이용해 표를 그려보겠습니다. 

	home[i][0]	home[i][1]	home[i][2]
i=1	26	40	83
i=2	49	60	57
i=3	13	89	99

입력으로 들어온 값을 2차원 배열 home에 저장한 모습입니다. 

현재 집을 R로 칠하는 경우의 값은, 이전 집은 G나 B로 칠하고 현재 R을 칠하는 비용을 합한 값입니다. 

점화식으로 나타내면 다음과 같습니다. 

dp[i][0]=min(dp[i-1][1], dp[i-1][2])+home[i][0]

G와 B도 같은 점화식을 사용하면 됩니다. 

점화식을 이용해 표를 그려보겠습니다. 

	dp[i][0]	dp[i][1]	dp[i][2]
i=1	min(dp[0][1],dp[0][2])+26=26	min(dp[0][0],dp[0][2])+40=40	min(dp[0][0],dp[0][1])+83=83
i=2	min(dp[1][1],dp[1][2])+49=89	min(dp[1][0],dp[1][2])+60=86	min(dp[1][0],dp[1][1])+57=83
i=3	min(dp[2][1],dp[0][2])+13=96	min(dp[2][0],dp[2][2])+89=172	min(dp[2][0],dp[2][1])+99=185

저희가 원하는 답은 96입니다. 

코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int min(int x, int y)
{
	return x < y ? x : y;
}

int main()
{
	int home[1001][3] = { 0 };
	int dp[1001][3] = { 0 };
	int T;

	cin >> T;
	for (int i = 1;i <= T;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> home[i][j];
		}
	}

	for (int i = 1;i <= T;i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + home[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + home[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + home[i][2];
	}

	cout << min(min(dp[T][0], dp[T][1]), dp[T][2]);

	return 0;
}