RGB거리 2 (백준 17404)

안녕하세요. 오늘은 원형 DP를 풀거예요.

문제

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

아이디어

이 문제는 기본 RGB거리 문제에 하나만 추가하면 됩니다.
바로 1번 집의 색깔입니다.
dp[i][j][k]를 1번집의 색깔을 i, j번집의 색깔을 k라고 했을 때 1번집부터 j번집까지를 다 색칠하는 최소비용이라고 정의합시다. 그러면 i를 고정시키고 dp[i][j][k]는 dp[i][j-1][1,2,3중 k를 제외한 두 수]+(j번 집을 k색으로 칠하는 비용)의 최솟값이 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll dp[4][1010][4] = { 0 }; //dp[i][j][k]: 1번째 집을 i색으로 칠하고 j번째 집을 k로 칠하는 최솟값

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, j, k, l, a, b ,c;

    for (i = 1; i <= 3; i++)
        for (j = 1; j <= 1000; j++)
            for (k = 1; k <= 3; k++)
                dp[i][j][k] = 2e9;

    cin >> N >> a >> b>> c;
    dp[1][1][1] = a; dp[2][1][2] = b; dp[3][1][3] = c;
    for (j = 2; j <= N; j++)
    {
        cin >> a >> b >> c;
        ll arr[4] = { 0,a,b,c };
        for (i = 1; i <= 3; i++)
        {
            for (k = 1; k <= 3; k++)
            {
                for (l = 1; l <= 3; l++)
                {
                    if (k == l) continue;
                    dp[i][j][k] = min(dp[i][j - 1][l] + arr[k], dp[i][j][k]);
                }
            }
        }
    }

    cout << min({ dp[1][N][2],dp[1][N][3],dp[2][N][1],dp[2][N][3],dp[3][N][1],dp[3][N][2] });
}

감사합니다.