[백준] [C/C++] [★] 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보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

예제 입력 2

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

예제 출력 2

208

알고리즘 [ 접근 방법 ]

DP문제이고 앞서 풀어본 문제 백준 15990번 : 1,2,3 더하기 5 문제와 굉장히 유사하다.

문제의 조건을 정리해보면 “연속한 집은 같은 색을 가질수 없다” 는 말이다.

주어진 문제를 점화식으로 표현해보면 다음과 같다.

D[i][j] = i번째 집을 j색으로 칠했을때, 1~i까지 색깔을 칠하는 비용의 최솟값

이때 j=0,1,2 는 각각 R,G,B를 의미한다.

A[i][j] = i번째집에 j색을 칠하는 비용

i번째 집이 0(=Red)으로 칠해진 경우에는 i-1번째집이 1로 칠해진 경우와 2로 칠해진 경우중 더 큰값을 구하고 이에 i번째 집에 0으로 칠하는 경우를 더해주면 된다.

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

D[i][0] = max( D[i-1][1] , D[i-1][2] ) + A[i][0]
D[i][1] = max( D[i-1][0] , D[i-1][2] ) + A[i][1]
D[i][2] = max( D[i-1][0] , D[i-1][1] ) + A[i][2]

이제 이를 코드로 보이면 된다.

풀이

#include <iostream>
#include <algorithm>
using namespace std;

int color[1001][3];
int d[1001][3]; // i번째집을 j로 칠했을 때, 1~i까지 칠하는 비용의 최솟값
				// 0=R, 1=G, 2=B

int main() {

	int test;
	cin >> test;

	for (int i = 1; i <= test; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> color[i][j];
		}
	}

	for (int i = 1; i <= test; i++) {
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + color[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + color[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + color[i][2];
	}
	
	// min이나 max에 인자가 3개들어가는 경우에는 괄호안에 대괄호를 넣어주면 된다.
	int res = min({ d[test][0], d[test][1], d[test][2] });
	
	cout << res << endl;


}