BOJ 17404 : RGB거리 2

문제링크

풀이 요약

DP

풀이 상세

1. 맨 처음 집의 경우를 빨간색, 초록색, 파란색으로 나올 경우로 하여 3번의 탐색을 진행한다. 최소의 값을 쉽게 판별하도
2. 만약 현재의 값이 빨간이 반영되어야 하는 경우, 이전까지의 초록과 파랑의 값 가운데 더 작은 값을 현재 빨간의 비용과 합하여 저장한다.
3. 마지막 집은 처음 집과 일치하면 안되기 때문에, 해당 경우는 조건에서 제외한다.

#include <iostream>
using namespace std;
int a[1004][3], dp[3][1004][3];
int N, ans;
const int MAX = 1000 * 1000 + 4;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
}

void go() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][0][j] = i == j ? a[0][j] : MAX;
        }

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

void output() {
    ans = MAX;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(i!=j) ans = min(dp[i][N-1][j], ans);
        }
    }
    cout << ans;
}

int main() {
    input();
    go();
    output();
}