[백준]RGB거리 - 복습 DP

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

모든 경우의수를 계산하면 당연히 시간초과가 난다 (제한시간 0.5s)
인접한 집은 같은 색으로 칠 할 수 없다

지금 집을 Red로 칠했으면 다음 집은 Green or Blue

.
.
.
5
4
3
2 40 + 49  26 + 60  26 + 57
1 26         40         83
   R          G          B

이런 테이블을 기본으로
2번 집 부터 빨강을 칠한다고 생각했을때 1번집에서 가능한 G, B중 낮은값을 가져온다
이전 누적 값 중 낮은 값을 그대로 가져와도 반례는 없다. 어짜피 다음 집 색과 겹치지만 않으면 되기 때문

#include <iostream>
#include <algorithm>

using namespace std;

int input[1001][4];
int dp[1001][4];

int INF = 987654321;

int main()
{
    int N;
    cin >> N;

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

    dp[1][1] = input[1][1];
    dp[1][2] = input[1][2];
    dp[1][3] = input[1][3];

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

    int ret = INF;
    for (int i = 1; i <= 3; i++)
    {
        if (dp[N][i] < ret)
            ret = dp[N][i];
    }

    cout << ret << endl;
}