백준 / 1149 / RGB거리 / C++

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

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> originval;
vector<vector<int>> dp;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    cin >> n;
    originval.resize(n, vector<int>(3));
    dp.resize(n, vector<int>(3, INT_MAX));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> originval[i][j];
        }
    }
    for(int i = 0; i < 3; i++)
    {
        dp[0][i] = originval[0][i]; // 초기값 입력
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < 3; j++) // n-1번째 인덱스
        {
            for (int k = 0; k < 3; k++) // n번째 인덱스
            {
                if (j == k)
                {
                    continue;
                }
                dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + originval[i + 1][k]);
            }
        }
    }
    cout << min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    return 0;
}

일반적인 DFS로 각 단계로 내려갈때마다 2개의 경우를 체크한 후 최솟값을 갱신하는 방법이 있지만, N개의 단계가 있다면 시간복잡도가 O(2^N)이기에 시간 내에 풀 수 없다. 그래서 DP를 이용해 N-1층에서 자신의 인덱스를 제외한 N층의 값을 확인한 후, 현재 N-1층의 값과 선택한 N층 값의 합이 현재 값보다 작다면 값을 갱신하도록 구현하였다.

구상한 로직을 예제 입력 1에 적용했을 때의 모습이다. 점화식은
dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + originval[i + 1][k]);
로 작성했다.