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

출력

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

---

동적계획법을 이용하는 문제.

앞의 유형들과 다를 것 없이 풀면 된다.

 

각 집의 R, G, B 비용별로 합을 구한 뒤 그 중 가장 작은 값이 총 비용이 된다.

이 때, i번째 집의 색은 i - 1번, i + 1번 집의 색과 같지 않아야 하는 조건때문에

 

- i번째 집의 R비용은 (i - 1)번째까지의 G비용과 B비용의 합 중 더 작은 값

- i번째 집의 G비용은 (i - 1)번째까지의 R비용과 B비용의 합 중 더 작은 값

- i번째 집의 B비용은 (i - 1)번째까지의 R비용과 G비용의 합 중 더 작은 값

 

에 각각 더해주면 된다.

 

이를 식으로 표현하면 다음과 같다.

sum[i][R] = min(sum[i - 1][G], sum[i - 1][B]) + color[i][R]

sum[i][G] = min(sum[i - 1][R], sum[i - 1][B]) + color[i][G]

sum[i][B] = min(sum[i - 1][R], sum[i - 1][G]) + color[i][B]

 

코드

#include <cstdio>
#define MAX 1001

int N;
int color[MAX][3];
// [i][0] : R, [i][1] : G, [i][2] : B
int DP();
int min(int a, int b) {
    return (a < b ? a : b);
}
int main(void) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for(int j = 0; j < 3; j++) {
            scanf("%d", &color[i][j]);
        }
    }

    printf("%d\n", DP());
    return 0;
}

int DP() {
    int sum[MAX][3];
    for(int i = 0; i < 3; i++) {
        sum[0][i] = color[0][i];
    }
    
    for(int i = 1; i < N; i++) {
        sum[i][0] = min(sum[i - 1][1], sum[i - 1][2]) + color[i][0];
        sum[i][1] = min(sum[i - 1][0], sum[i - 1][2]) + color[i][1];
        sum[i][2] = min(sum[i - 1][0], sum[i - 1][1]) + color[i][2];
    }

    int result = min(min(sum[N - 1][0], sum[N - 1][1]), sum[N - 1][2]);

    return result;
}