[C++] BOJ / 1149번 / RGB거리

1149번: 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보다 작거나 같은 자연수이다.

 

출력

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

 

 

풀이

26 40 83
49 60 57
13 89 99

 

위의 경우를 예를 들어 설명해보겠습니다.  위의 숫자들의 의미는 다음과 같습니다.

첫 번째 집을 빨강, 초록, 파랑으로 칠하는 비용은 각각 26, 40, 83 입니다.

두 번째 집을 빨강, 초록, 파랑으로 칠하는 비용은 각각 49, 60, 57 입니다.

세 번째 집을 빨강, 초록, 파랑으로 칠하는 비용은 각각 13, 89, 99 입니다.

 

문제의 조건은 얼핏 보면 복잡해 보일 수 있지만 그냥 연속된 두 집은 서로 같은 색을 칠할 수 없다라고 정의할 수 있습니다. 집의 최소 개수는 2개이기 때문에 두 번째 집을 기준으로 살펴보도록 하겠습니다.

 

두 번째 집을 빨강으로 칠하는 최소 비용은 첫 번째 집을 초록 또는 파랑으로 칠하는 비용 중 최솟값과 더하여 구할 수 있습니다. 즉, min(40, 83) = 40 이기 때문에 89(40 + 49)로 최소 비용을 구할 수 있습니다.

마찬가지로 두 번째 집을 초록으로 칠하는 최소 비용과 파랑으로 칠하는 최소 비용을 각각 구할 수 있으며 모두 계산한 이후 배열을 다음과 같아집니다.

 

26 40 83
89 86 83
13 89 99

 

이번에는 세 번째 집을 각각의 색상으로 칠하였을 때 최소 비용을 구해보도록 하겠습니다.

세 번째 집을 빨강으로 칠하는 최소 비용은 두 번째 집을 초록 또는 파랑으로 칠하는 비용 중 최솟값과 더하여 구할 수 있습니다. 즉, min(86, 83) = 83 이기 때문에 96(83 + 13)으로 최소 비용을 구할 수 있습니다.

마찬가지로 세 번째 집을 초록, 파랑으로 칠하는 최소 비용을 각각 구할 수 있으며 모두 계산한 이후 배열은 다음과 같아집니다.

 

26 40 83
89 86 83
96 172 185

 

따라서 조건에 맞게 모든 집을 칠하는 최소 비용은 96 이라는 것을 확인할 수 있습니다.

 

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

 

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

---

#include <iostream>

using namespace std;

#define MAX 1000
#define endl '\n'

int DP[MAX + 1][3];

int main()
{
	int n;

	cin >> n;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < 3; ++j)
			cin >> DP[i][j];

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

	int ans = MAX * n;
	for (int i = 0; i < 3; ++i)
		if (ans > DP[n][i])
			ans = DP[n][i];

	cout << ans << endl;
}