[백준 / C++] 1149 - RGB거리

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

1149번: RGB거리

서로 이웃한 집과 같은 색이 아니면 된다. 그래서 n개의 집을 3가지 색으로 칠하는 dp[n][3]를 정의한다. 이를 0부터 n - 1까지 그리고 RGB 순으로 반복을 돌린다. k번째 집을 RGB 3종류로 칠한다고 각각 가정하고 이와 다른 색들로 칠해진 k - 1번째 집들 중 최소를 찾아 그 집을 칠할 때 드는 비용과 더해준다. 그리고 마지막에 최소값을 찾아 출력한다.

#include <iostream>
#define MAX 1001
#define INF 100000000
using namespace std;

int dp[MAX][3], arr[MAX][3];
int ans = INF;
int n, tmp;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            dp[i][j] = INF;

    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            tmp = INF;
            for (int k = 0; k < 3; k++)
                if (j != k)
                    tmp = min(tmp, dp[i - 1][k]);
           dp[i][j] = tmp + arr[i][j];
        }
    }

    for (int i = 0; i < 3; i++)
        ans = min(ans, dp[n - 1][i]);
    cout << ans << "\n";

    return 0;
}