[C++] RGB거리 2 (백준 17404번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int MAXV = 1000 * 1000 + 1;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> rgb(n + 1, vector<int>(3));
    for (int i = 1; i < n + 1; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> rgb[i][j];
        }
    }

    vector<vector<int>> dp(n + 1, vector<int>(3));
    int ans = MAXV;

    // 첫번째 집이 각각 r, g, b일 때로 나눠서 dp 채우기
    for (int first = 0; first < 3; first++) {
        for (int j = 0; j < 3; j++) {
            if (j == first) dp[1][j] = rgb[1][j];
            else dp[1][j] = MAXV;
        }

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

        for (int j = 0; j < 3; j++) {
            if (j != first) ans = min(ans, dp[n][j]);
        }
    }

    cout << ans << '\n';
}

이 문제는 RGB거리 문제의 2탄이다. https://www.acmicpc.net/problem/1149

원래 문제에서는 RGB 거리, 즉 집들이 놓여있는 거리가 선형의 형태를 띄고 있었다. 그래서 dp를 다음과 같이 정의한 후 채우면 됐다. 

dp[i][j] : i번째 집을 색상 j로 칠했을 때의 최소 비용

RGB 거리 2에서 바뀐 것은 RGB 거리가 원형으로 이루어져 있다는 것이다. 이는 N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다는 뜻이다. 따라서 첫번째 집이 각각 r, g, b일 때로 나눠서 dp 테이블을 각각 채워야 한다. (AC)