[백준/C++] RGB거리

1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

문제유형

*다이나믹 프로그래밍

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입출력 예제

 

(입력 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

풀이

1. 위 문제는 동적프로그래밍 문제이므로, 작은 문제로 쪼개어서 진행을 해야 한다. 따라서, 위 문제를 작은 문제로 쪼개어보면 i번째 집을 빨강, 초록, 파랑 중의 한 색으로 칠했을 때의 최솟값을 구해야 한다. 

2. 먼저, i번째 집에서의 각 색깔의 값을 저장할 배열 color[1001][3]을 선언한다.

3. for문을 통해 1부터 n번째까지의 값을 입력받는다.

4. 최솟값을 구하기 위해서, 다시 for문을 통해 2부터 N번째까지, 위 조건을 만족하는 최솟값을 배열에 갱신한다.

5. 최종적으로 n번째 배열에서의 값끼리 비교를 해서 최솟값을 구할 수 있다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int color[1001][3];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i=1; i<=N; i++) 
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    
    for (int i=2; i<=N; i++) {
        color[i][0] += min(color[i-1][1], color[i-1][2]);
        color[i][1] += min(color[i-1][0], color[i-1][2]);
        color[i][2] += min(color[i-1][0], color[i-1][1]);
    }
    
    int cost = min(min(color[N][0], color[N][1]), color[N][2]);
    cout << cost;
    
	return 0;
}