[Baekjoon/C++] 17404번 - RGB거리 2

[백준] Baekjoon Online Judge

문제로 이동

 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

#define MAX 987654321

int N, result = MAX;
int house[1000][3];
int dp[1000][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    for (int rgb = 0; rgb < 3; rgb++) {
    	// 첫번째 집의 색상 정하기
        dp[0][0] = dp[0][1] = dp[0][2] = MAX;
        dp[0][rgb] = house[0][rgb];
        
        // 각 집의 색상 정하기
        for (int i = 1; i < N; i++) {
            dp[i][0] = house[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = house[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = house[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
        }

        for (int i = 0; i < 3; i++) {
            // 첫번째 집과 색이 겹치지 않는 경우
            if (i != rgb) result = min(result, dp[N - 1][i]);
        }
    }

    cout << result << '\n';

    return 0;
}

 해당 문제에서는 첫번째 집과 마지막 집의 선택이 중요하며, 특히 첫번째 집이 어떤 색을 선택하는지에 따라 결과에 차이가 발생할 수 있다. 그렇기에 첫번째 집의 색을 확정한 뒤 이에 따른 결과를 모두 비교하는 방식으로 문제를 풀었다.