[C++] 백준 17404 RGB거리 2

#include <iostream>
#include <algorithm>
 
int cost[1001][3] = {};
 
int main() 
{
    int N = 0;
    std::cin >> N;
 
    int ans = 2147483647;
 
    for (int i = 1; i <= N; ++i) 
    {
        std::cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }
 
    for (int i = 0; i <= 2; ++i) 
    {
        int dp[1001][3] = {};
 
        for (int j = 0; j <= 2; ++j) 
        {
            if (j == i)
                dp[1][i] = cost[1][i];
 
            else 
                dp[1][j] = 2147483647 / 2;
        }
 
        for (int z = 2; z <= N; ++z) 
        {
            dp[z][0] = std::min(dp[z - 1][1], dp[z - 1][2]) + cost[z][0];
            dp[z][1] = std::min(dp[z - 1][0], dp[z - 1][2]) + cost[z][1];
            dp[z][2] = std::min(dp[z - 1][1], dp[z - 1][0]) + cost[z][2];
        }
 
        for (int j = 0; j <= 2; ++j) 
        {
            if (j == i) 
                continue;
 
            ans = std::min(ans, dp[N][j]);
        }
    }
 
    std::cout << ans;
 
    return 0;
}

마지막과 처음이 다르면 안된다라는 게 이 문제의 키 포인트 입니다.

키포인트는 DP로 처음을 정해놓고 마지막이 똑같을 경우 continue로 넘기도록 했습니다.

 

문제 풀이로는 문제 그대로 바로 옆에 있는 수만 아니면 되기 때문에

0번일 경우 1,2 중에 가장 적은 것을 고르도록 하면서 진행했습니다.

마지막에 continue를 이용해서 같은 색만 아니게 만들면 됩니다.