백준[17404] RGB거리 2

문제 설명

풀이

이 문제는 RGB거리와 똑같이 dp문제지만 이 문제는 마지막 집과 1번 집이 연결되어 있다. 그렇기 때문에 첫 번째 집을 고정시켜 n번째에 첫 번째 색과 같은 경우를 배제시켜야 한다.

dp[i][j] = i - 1에서 현재 색이 아닌 경우의 최소 + arr[i][j] (i : 현재 위치, j : 현재 색)

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int arr[1002][3];
int dp[1002][3];

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < 3; j++) 
            scanf("%d", &arr[i][j]);

    int ans = 1e9;
    for (int k = 0; k < 3; k++) {
        for (int i = 1; i <= n; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
            // 첫번째 색을 고정시킨다
            if (i == 1) {
                for (int j = 0; j < 3; j++) if (j != k) dp[i][j] = 1e9;
            }
            // n번째에 첫번째와 색이 같은 경우를 배제시킨다.
            if (i == n) dp[i][k] = 1e9;
        }
        ans = min(ans, min(dp[n][0], min(dp[n][1], dp[n][2])));
    }
    printf("%d", ans);
}

문제 링크: https://www.acmicpc.net/problem/17404