백준 1149 RGB 거리 C++

문제

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

출처

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: djm03178
• 문제의 오타를 찾은 사람: fail456
• 데이터를 추가한 사람: rdd6584

알고리즘 분류

• 다이나믹 프로그래밍

내 풀이

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

int n, minimum_cost;

int house[1001][3]; //house[번호] = {R의 비용, G의 비용, B의 비용}
int cost[1001][3]; //cost => cost가 얼마정도인지 RGB종류별로 (R = 0, G = 1, B = 2)}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> house[i][0] >> house[i][1] >> house[i][2]; 
	}
	
	cost[1][0] = house[1][0];
	cost[1][1] = house[1][1];
	cost[1][2] = house[1][2];

	//R, G, B별로 최단비용을 각각 구해야 한다.
	for (int i = 2; i <= n; i++) {
		cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + house[i][0]; //R일경우 이전은 G, B
		cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + house[i][1]; //G일 경우 이전은 R, B
		cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + house[i][2]; //B일 경우 이전은 R, G
	}
  
	minimum_cost = min(cost[n][0], cost[n][1]); //최종  R, G, B가격중 최소 
	minimum_cost = min(minimum_cost, cost[n][2]);
	cout << minimum_cost;
}

풀이를 들으면 쉽다.

처음 아이디어를 떠올리기 쉽지 않아 많이 풀어봐야 된다.