[백준 / C++] RGB거리(실버1, 1149)

문제

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

---

문제 풀이

이번 문제는 주어진 모든 집을 최소한의 비용을 사용해 R, G, B 색상으로 칠해야 하는 문제입니다.

 

간단히 생각하면 연속된 집은 같은 색상을 가질 수 없기에 모든 경우의 수를 체크해보며 최소 비용을 구해야합니다.

 

하지만, 집이 최대 1000개가 존재할 수 있기에 모든 집을 다른 색상으로 칠해보며 비용을 계산하는 방식으로는 시간이 오버되며, 이를 해결하기 위해 케이스별 최적의 해를 저장해야 하는 DP 문제입니다.

 

예를 들어보면 다음과 같습니다.

 

위와 같이 1번 집과 2번집이 존재한다고 가정해보도록 하겠습니다.

케이스별 최적의 해를 저장해야 하므로, 2번 집(현재 집)에서 R or G or B 를 선택했을 때 각각의 최소 값을 구해야 합니다.

 

2번 집에서 R을 선택한다고 했을 경우 1번 집과의 색이 겹치면 안되므로 1번 집에서는 G와 B를 선택할 수 있습니다.

즉, 1번 집에서 G(40)를 선택한 값이 B(83)을 선택한 값보다 적으므로 G를 선택하는 것이 최적의 해라는 것을 알 수 있습니다.

 

위와 동일하게 2번 집에서의 R, G, B 값을 전부 구했다면 2번 집까지의 값을 업데이트 해주도록 합니다.

업데이트 된 최소 비용 값

 

다음으로 3번 집으로 넘어가 위 작업을 다시 반복해줍니다.

3번도 이전과 같이 연산을 해주면 다음과 같습니다.

• R을 선택할 수 있는 최소 비용은 83 + 13 = 96
• G를 선택할 수 있는 최소 비용은 83 + 89 = 172
• B를 선택할 수 있는 최소 비용은 86 + 99 = 185 

즉, 3번 집까지 존재하는 예제 1번의 케이스에서 3번 집의 R을 선택하는 최소 비용(83)이 결국 모든 집을 칠하는 최소 비용인 것을 알 수 있습니다.

 

위 아이디어를 코드로 옮겨 작성해주면 다음과 같습니다.

코드

#include <iostream>

using namespace std;

int n;
int arr[1002][3];

int prices[1002][3];

void Go(int num)
{
	if (num == n) return;

	prices[num][0] = min(prices[num - 1][1], prices[num - 1][2]) + arr[num][0];
	prices[num][1] = min(prices[num - 1][0], prices[num - 1][2]) + arr[num][1];
	prices[num][2] = min(prices[num - 1][0], prices[num - 1][1]) + arr[num][2];

	Go(num + 1);
}

int main()
{
	// 입력
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int temp = 0;
			cin >> temp;

			arr[i][j] = temp;
		}
	}

	prices[0][0] = 0;
	prices[0][1] = 0;
	prices[0][2] = 0;

	Go(0);

	int res = min(min(prices[n - 1][0], prices[n - 1][1]), prices[n - 1][2]);

	cout << res;
}