[백준] 17404번: RGB거리 2

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

17404번: RGB거리 2

 

처음에는 이렇게 구현했는데 주어진 테스트케이스에서 첫번째 테스트케이스만 통과를 못했다.

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int arr[3][1001];
    int dp[3][1001];
    int lastColor[3] = {0, 1, 2};

    cin >> n;

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

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

    for (int i = 1; i < n; i++) {
        dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + arr[0][i];
        dp[1][i] = min(dp[0][i - 1], dp[2][i - 1]) + arr[1][i];
        dp[2][i] = min(dp[0][i - 1], dp[1][i - 1]) + arr[2][i];
    }

    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < 3; j++) {
            if (lastColor[j] == 0) {
                if (dp[1][i - 1] < dp[2][i - 1]) {
                    lastColor[j] = 1;
                } else {
                    lastColor[j] = 2;
                }
            } else if (lastColor[j] == 1) {
                if (dp[0][i - 1] < dp[2][i - 1]) {
                    lastColor[j] = 0;
                } else {
                    lastColor[j] = 2;
                }
            } else {
                if (dp[0][i - 1] < dp[1][i - 1]) {
                    lastColor[j] = 0;
                } else {
                    lastColor[j] = 1;
                }
            }
        }
    }

    int ans = 1000000;

    for (int i = 0; i < 3; i++) {
        if (lastColor[i] != i) {
            ans = min(ans, dp[i][n - 1]);
        }
    }

    cout << ans << "\n";

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << dp[i][j] << " ";
        }

        cout << "\n";
    }

    return 0;
}

 

위의 풀이는 다음과 같은 문제가 있었다.

26 40 83

40 60 57

13 89 99

 

dp배열은 다음과 같다.

26 40 83
89 86 83
96 172 185

 

따라서 가장 작은 비용은 26 + 57 + 13 = 96 이지만,

1번 N번 집의 색이 달라야 하므로 조건을 만족하는 그 다음 작은 비용인 172가 출력된다.

하지만 정답은 40 + 53 + 13 = 110 이다ㅋㅋㅠㅠㅠ

 

그래서 그냥 1번째 집 색깔을 고정해놓고 풀었다.. 

dp[0][0] = arr[0][0];

dp[1][0] = MAX;

dp[2][0] = MAX; 

이런식으로..