[백준/C++] RGB거리

RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

풀이

집의 수가 N개일 때, N-1개까지의 최소비용에 현재 행에서 최솟값을 더해(이전에 색칠했던 색 제외)주면 되기 때문에 부분문제로부터 전체의 답을 얻을 수 있다. 또, 비둘기집의 원리에 따라 중복되는 경우는 존재한다. 그러므로 이 문제는 DP로 풀 수 있다.

그 직전에 무슨 색을 칠했는지에 따라서 현재의 비용이 달라지므로 매개변수 하나만 가지고 점화식을 세울 수는 없고, 직전에 무슨 색을 칠했는가를 0,1,2,3으로 표시해야 한다.

D[n][L] = min(D[n - 1][?] + arr[n][L], D[n - 1][?] + arr[n][L]);

이 정도가 되겠다.

#include <iostream>
using namespace std;

int cache[1001][3], arr[1001][3];

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < 3; ++j) {
			cin >> arr[i][j];
			if(i == 1) cache[1][j] = arr[i][j];
		}
	}

	for(int i = 2; i <=n; ++i) {
		for(int j = 0; j < 3; ++j) {
			if(j == 0) cache[i][j] = min(cache[i - 1][1] + arr[i][j], cache[i - 1][2] + arr[i][j]);
			if(j == 1) cache[i][j] = min(cache[i - 1][0] + arr[i][j], cache[i - 1][2] + arr[i][j]);
			if(j == 2) cache[i][j] = min(cache[i - 1][0] + arr[i][j], cache[i - 1][1] + arr[i][j]);
		}
	}

	int MIN = 1000001;
	for(int i = 0; i < 3; ++i)
		MIN = min(MIN, cache[n][i]);

	cout << MIN;
	return 0;
}

끝