/<> 백준 17404번 : RGB거리 2 (C언어)

https://www.acmicpc.net/problem/17404

 

 

<1149번 : RGB거리> 문제와 흡사하게 다이나믹 프로그래밍(DP)을 사용하는 문제입니다.

근접한 집들끼린 같은 색으로 칠하지 않아야 하는데, 추가로 처음 집과 마지막 집의 색도 달라야 합니다.

 

처음에 문제를 풀 때 첫번째 집의 색의 정보를 저장한 배열을 따로 만들어 DP를 실행할 때마다 새로 저장을 했습니다.  너무 복잡하고 연산이 뜻대로 되지 않았습니다.

 

다시 문제를 풀 때 dp[n - 1][i]의 처음 집 색을 구하고 n번째 집의 색을 다른 두 가지 중 cost가 낮은 색을 택하려고 했습니다. 하지만 처음 시도와 달리 첫 집의 색을 저장하지 않아 답이 안 나왔습니다.

 

그래서 처음부터 집 색을 하나 정하고, 그다음에 DP를 진행하여 마지막 집의 색을 처음 색과 다른 것을 택하도록 했습니다. 그럼 색이 3종류이니 총 3번(첫 집 색이 R or G or B) 반복문을 돌리면 됩니다.

 

 

<코드>

#include <stdio.h>

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

int min(int a, int b) {
    return a < b ? a : b;
}

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

    int result = 10000000;

    // 첫 번째 집의 색을 미리 정하기
    for (int first_color = 0; first_color < 3; first_color++) {
        // DP 배열 초기화
        for (int i = 0; i < 3; i++) {
            if (i == first_color) dp[0][i] = rgb[0][i];
            else dp[0][i] = 10000000;
        }

        // 나머지 비용 계산
        for (int i = 1; i < n; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + rgb[i][2];
        }

        // 마지막 집의 색이 첫 번째 집의 색과 달라야 함
        for (int last_color = 0; last_color < 3; last_color++) {
            if (first_color != last_color) {
                result = min(result, dp[n - 1][last_color]);
            }
        }
    }

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

 

 

int 연산이 편하므로 집의 색을 R, G, B 순으로 각 1, 2, 3으로 넘버링을 하고 반복문을 진행합니다.