[백준][C++] 17404: RGB거리 2

문제

풀이

다이나믹 프로그래밍을 사용한다.

• N번 집을 칠할 때, 1번 집의 색의 영향을 받는다.
• 1번 집을 R로 칠한 경우, G로 칠한 경우, B로 칠한 경우 세 가지를 모두 검사해야 한다.
• 1번 집을 칠한 색이외의 cache에는 충분히 큰 값을 두어 2번 집을 칠할 때 선택되지 않도록 해야한다. 
• i번 집을 j색으로 칠했을 때의 최솟값은 i번 집을 j색으로 칠한 비용과 i - 1번 집을 j 이외의 색으로 칠한 비용의 합의 최솟값이다. 
• N번 집은 1번 집을 칠했을 때의 색으론 칠할 수 없으니 그 경우는 제외해야 한다.

코드

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int house[1001][3];
int cache[1001][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N;
    cin >> N;

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

    // 첫번째 집에서 R을 선택했을 때, G를 선택했을 때, B를 선택했을 때
    // 3가지 경우를 비교한다.
    int color = 0;
    int answer = INT_MAX;
    while (color < 3)
    {
        // 선택한 색 외에는 충분히 큰 값으로 설정
        cache[0][color] = house[0][color];
        cache[0][(color + 1) % 3] = 10000;
        cache[0][(color + 2) % 3] = 10000;

        // 이전 집들 중 자신의 색과 다른 색의 경우만 비교한다.
        for (int i = 1; i < N; ++i)
        {
            cache[i][0] = min(house[i][0] + cache[i - 1][1], house[i][0] + cache[i - 1][2]);
            cache[i][1] = min(house[i][1] + cache[i - 1][0], house[i][1] + cache[i - 1][2]);
            cache[i][2] = min(house[i][2] + cache[i - 1][0], house[i][2] + cache[i - 1][1]);
        }

        for (int i = 0; i < 3; ++i)
        {
            // 마지막 집과 첫번째 집이 동일한 색인 경우는 제외한다.
            if (i == color)
            {
                continue;
            }

            answer = min(answer, cache[N - 1][i]);
        }

        // 다음 색으로 넘어간다.
        color++;
    }

    cout << answer;

    return 0;
}