[C++] 백준/Gold/17404. RGB거리 2

문제 링크

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

문제 분석

비슷한 유형의 RGB 거리보다 조금 더 심화된 DP 문제라고 할 수 있다.
이전 문제에서 각 1번째 집의 색깔이 마지막 집(N-1)의 색과 동일하면 안 된다는 조건이 추가된 응용 버전인데, 시작을 1번째 집의 색깔을 R, G, B로 선택했을 때 각각에 대한 DP 배열을 이전 문제와 같이 채우면 되는 문제이다.

DP 배열 구성

DP 배열의 크기는 3(1번째 집의 색깔을 고르는 경우의 수) * n * 3이다.
1번째 집의 색을 R로 선택했을 때의 경우를 예로 들면, 2번째 집에서는 1번째 집의 G, B에 해당하는 값을 선택하면 안 된다.
여기서 아이디어가 필요한데, 본인은 DP 배열에서 1번째에서 선택한 집을 제외한 나머지를 임의의 높은 값(9999)로 설정해줌으로써, 2번째 집에서 1번째 집을 제외한 나머지 집을 선택하는 경우를 없앴다.

핵심 아이디어

1번째 집에서 R을 선택했을 때, G와 B를 선택하는 경우는 자연스럽게 도태된다.
이러한 방식을 통해 시작 색깔에 따른 모든 경우를 탐색하며 최소값을 구한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> v(n, vector<int>(3));
    for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1] >> v[i][2];
    vector<vector<vector<int>>> dp(3, vector<vector<int>>(n, vector<int>(3)));
    int answer = INT_MAX;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == j) continue;
            dp[i][0][j] = 9999;
        }
        dp[i][0][i] = v[0][i];
        for (int j = 1; j < n; j++) {
            dp[i][j][0] = min(dp[i][j - 1][1], dp[i][j - 1][2]) + v[j][0];
            dp[i][j][1] = min(dp[i][j - 1][0], dp[i][j - 1][2]) + v[j][1];
            dp[i][j][2] = min(dp[i][j - 1][0], dp[i][j - 1][1]) + v[j][2];
        }
        for (int j = 0; j < 3; j++) {
            if (i == j) continue;
            answer = min(answer, dp[i][n - 1][j]);
        }
    }

    cout << answer;
}