백준 1149 : RGB거리

문제 설명

---

RGB 거리에는 집이 여러 채 있고, 각 집을 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다. 각각의 집을 칠하는 비용이 주어지며, 인접한 두 집이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 데 드는 최소 비용을(n ≤ 1,000)구하는 문제이다.

---

 

 인접한 두 집이 서로 같은 색이 되지 않도록 칠해야 함에 주의하자. Dp[i][j] = "i번째집을 j색으로 칠할때 드는 최소비용"으로 정의 한다면 점화식은 다음과 같다.

 

• dp[i][k] = min(dp[i][k], dp[i-1][j] + arr[i][k])
• i번째 집을 색 k로 칠할 때의 최소 비용은 i-1번째 집을 j 색으로 칠한 비용에 i번째 집을 k 색으로 칠하는 비용을 더한 값 중 최소값으로 갱신한다.
• 단, j와 k가 같으면 안되므로 같은 색의 경우는 continue.

 

이를 바탕으로 문제를 풀어낼 수 있다.

 

---

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int dp[1010][5];
int arr[1010][5];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= 3; j++) {
			scanf("%d", &arr[i][j]);
			dp[i][j] = 2e9;
		}
	}
	dp[1][1] = arr[1][1];
	dp[1][2] = arr[1][2];
	dp[1][3] = arr[1][3];
	for (i = 2; i <= n; i++) {
		for (j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				if (j == k) continue;
				dp[i][k] = min(dp[i][k], dp[i - 1][j] + arr[i][k]);
			}
		}
	}
	int ans = 2e9;
	for (i = 1; i <= 3; i++) ans = min(ans, dp[n][i]);
	printf("%d", ans);
	return 0;
}