[백준/C++] 1149번 : RGB거리 (DP연습)

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

예제 입력 2 

3
1 100 100
100 1 100
100 100 1

예제 출력 2 

3

예제 입력 3 

3
1 100 100
100 100 100
1 100 100

예제 출력 3 

102

예제 입력 4 

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4 

208

예제 입력 5 

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5 

253

---

해당 문제를 보고 처음 생각해낸 풀이는 다음과 같다.

 

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int dp[1001]; 
	int color[1001]; // 0:r, 1:g, 2:b
	int N;
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		int rgb[3];
		cin >> rgb[0] >> rgb[1] >> rgb[2];
		int minIdx = min_element(begin(rgb), end(rgb)) - begin(rgb);
		if (i == 1)
		{
			dp[i] = rgb[minIdx];
			color[i] = minIdx;
		}
		else
		{
			rgb[color[i - 1]] = 9999;
			minIdx = min_element(begin(rgb), end(rgb)) - begin(rgb);
			dp[i] = dp[i - 1] + rgb[minIdx];
			color[i] = minIdx;
		}
	}

	cout << dp[N];
	return 0;
}

 

1. 비용 값(dp[1001])과 칠한 집의 색상 값(color[1001])을 저장하는 배열을 각각 만들어서 저장한다.

2. 이전 집과 색상이 겹치면 안되기 때문에 입력받은 rgb 중 이전집의 색상값은 최대 비용인 1000보다 더 큰 9999로 초기화한다.

3. rgb 색상 별 비용의 최솟값 Index를 찾고 dp[i] = dp[i-1] + rgb[minIndex] 를 더한다.

4. 색상값을 저장하는 배열 color에도 min Index를 초기화하여 갱신한다.

 

이렇게 풀이했을 때 예제 출력 1,2,3,4 전부 정답이 출력되었지만, 예제 5번에서 오답이 출력되었다.

원인은 N번 집을 칠할 때 N+1번집의 최솟값 Index와 동일한 경우, N+1번 집의 최소비용 색상을 칠하는것이 N번집의 최소비용 색상을 칠하는 것보다 더 이득인 경우가 존재했기 때문이다. 

내 코드는 N-1번집의 최소비용과 겹치지 않는 경우만 생각했기 때문에 N+1번 집의 상황까지 고려하지 못했다.

 

따라서 위의 코드를 버리고.. 최종적으로 풀이한 소스코드는 아래와 같다.

 

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int dp[1001][3]; // 0:r, 1:g, 2:b
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int rgb[3];
		cin >> rgb[0] >> rgb[1] >> rgb[2];

		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + rgb[2];
	}
	cout << min(dp[N][0], min(dp[N][1], dp[N][2]));
	return 0;
}

그냥 집에 모든 색상을 칠하는 경우의 수를 구해주면 된다..^^

다시한번 DP 문제를 풀때의 핵심은 "모든 경우의 수를 고려한다"라는 것을 깨닫는 시간이었다.. 나도 모르게 모든 경우의 수를 따지지 않고 효율적인 경우만 따지려고 해서 코드에 약점이 숨어있었다.

 

위 코드는 각 집을 빨강, 초록, 파랑으로 칠했을 때 이전 집이 빨강이 아닌경우, 초록이 아닌경우, 파랑이 아닌경우의 최솟값을 비교하여 각각 더해주었고, 마지막으로는 dp[N] 값이 각각의 색상 중 어느 색상으로 칠한 마지막 집이 가장 최소 비용인지를 따져 출력해주었다.