[백준] 1149 - RGB거리 (C언어)

SIVLER I

문제

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보다 작거나 같은 자연수이다.

출력

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

---

풀이

문제를 보자마자 동적 프로그래밍을 처음으로 배웠을 때 풀었던 문제인 돌놓기가 생각났다. 그 문제와는 고려해야할 조건이 조금 다르지만, 실질적으로 거의 같은 문제라고 볼 수 있다.

26 40 83
49 60 57
13 89 99

문제에서 입력이 이렇게 주어졌다면, 초기 dp 배열에는 26 40 83만 들어간다.

이후 두 번째부터가 중요한데, 각각 49 60 57을 선택했을 때, 얻을 수 있는 최솟값을 구하여 dp와 원래 배열과 같은 위치에 값을 삽입하면 된다. 예를 들어, 49일 때는, 40과 83 중 40이 더 작으므로 40을 선택하여 66이라는 값을 넣으면 된다. 그러므로, dp[1]에는 89 86 83이 들어간다.

이 과정을 n번 반복해서 dp[n-1]까지 가득 채운 후, dp[n-1]의 원소 중 최솟값이 이 문제의 해가 된다.

전체 코드

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    int rgb[1000][3];
    int dp[1000][3];

    for (int i = 0; i < n; i++)
        scanf("%d %d %d", &rgb[i][0], &rgb[i][1], &rgb[i][2]);

    dp[0][0] = rgb[0][0];
    dp[0][1] = rgb[0][1];
    dp[0][2] = rgb[0][2];

    for (int i = 1; i < n; i++) {
        for (int k = 0; k < 3; k++)
        {
            int tmp = dp[i-1][(k+1)%3] < dp[i-1][(k+2)%3] ? dp[i-1][(k+1)%3] : dp[i-1][(k+2)%3];
            dp[i][k] = tmp + rgb[i][k];
        }        
    }

    int answer = dp[n-1][0] < dp[n-1][1] ? dp[n-1][0] : dp[n-1][1];
    answer = answer < dp[n-1][2] ? answer : dp[n-1][2];

    printf("%d", answer);        

    return 0; 
}