[C++] 백준 1149번 RGB거리

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

풀이

처음에는 i번째 집의 색과 i+1번째 집의 색을 다르게 칠하는 모든 경우의 수를 BFS를 이용하여 탐색하고 최종적으로 N개의 집을 칠하는 최소 비용을 구하는 방식으로 구현했다. 그런데 이 방식은 경우의 수가 매우 커서 큐에 최대 3×2^(N-1)개의 노드가 저장된다. 그래서 BFS로 구현한 코드를 제출하면 메모리 초과가 발생한다.

따라서 탐색의 경우를 효과적으로 줄일 수 있는 점화식을 세우고 DP로 풀었다.
i번째 집을 j번째 색으로 칠한다고 하면, i-1번째 집은 j번째 색이 아닌 다른 두 색 중 하나로 칠해야 하고, 총 비용을 최소로 만들기 위해 더 저렴한 색을 선택해야 한다.

i번째 집을 j번째 색으로 칠하는 비용을 cost[j]라고 하고,
i번째 집을 j번째 색으로 칠했을 때 누적된 최소 비용을 dp[i][j]라고 하자.
점화식을 아래와 같이 만들 수 있다.

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[2]

dp[i] = min(dp[i][0], dp[i][1], dp[i][2])

실제 코드에서는 i번째 집을 j번째 색으로 칠할 때, {0, 1, 2} 중 j가 아닌 다른 두 수를 (j+1) % 3, (j+2) % 3 로 나타냈다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    int cost[3];
    vector<vector<int>> dp(N, vector<int>(3));
    for(int j=0; j<3; j++) cin >> dp[0][j];
    for(int i=1; i<N; i++) {
        for(int j=0; j<3; j++) cin >> cost[j];

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

    cout << min(min(dp[N-1][0], dp[N-1][1]), dp[N-1][2]);

    return 0;
}