[백준]17404번 RGB 거리 2

1. 문제

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

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

해당 조건을 만족하는 가장 최소의 비용을 구하면 된다.
입력은 첫째줄에 N, 둘째줄부터 빨강, 초록, 파랑순으로 집을 칠하는 비용이 주어진다.

2. 풀이

1149번 RGB 거리 문제에 첫번째 집과 N번째 집의 색도 같은 조건을 만족한다는 조건이 추가된 문제이다.

간단히 N개의 집이 원형으로 이어져 있다고 생각하면 될 듯 하다.

풀이는 간단하다. 첫번째 집이 세가지의 색 중에 한가지를 골라 칠해지는 경우를 가정하여 비용을 각각 계산해보고 최소값을 구하면 된다.

이렇게 하면 첫번째 집의 색을 무엇을 칠했는지 알기에 마지막 집의 색도 결정할 수 있기 때문이다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lst[1000][3], N, minNum = 1000 * 1000 + 1;

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

    int dp[1000][3] = {0};
    for (int s = 0; s < 3; ++s)
    {
        for (int i = 0; i < 3; ++i)
        {
            if (s == i) dp[0][i] = lst[0][i];
            else dp[0][i] = 1000 * 1000 + 1;
        }

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

        for (int i = 0; i < 3; ++i)
        {
            if (i == s) continue;
            minNum = min(minNum, dp[N - 1][i]);
        }
    }

    cout << minNum;
}

4. 후기

항상 그랬듯이 어려운 문제는 아니지만 아이디어를 떠올리는 것이 어려웠다.

문제를 풀고난 뒤, 이런 식으로 알고리즘을 전개해 나가면 되겠구나 했던 문제였다.

역시 골드 단계에 올라가있는 문제들은 적당히 쉬운게 없다.