[백준/BOJ] 1149번 RGB거리 (C++)

www.acmicpc.net/problem/1149

1149번: RGB거리

DP 유형의 문제입니다.

입력값의 각 열은 R, G, B 색깔, 행은 집의 수를 의미합니다. 문제의 조건은 결국 같은 색이 인접하면 안된다는 것을 의미합니다. 따라서 n번째 집의 색이 R, G, B 였을 때 n-1의 색이 다른 색이 되게끔, 최소값을 가지게끔 만들면 됩니다. 그런데 색깔에 따라 점화식을 만들어내야하므로, 2차원 dp배열을 이용하면 다음과 같은 점화식을 만들 수 있습니다.

 

dp[n][0] = min(dp[n - 1][1], dp[n - 2][2]) + map[n][0]

dp[n][1] = min(dp[n - 1][0], dp[n - 2][2]) + map[n][1]

dp[n][2] = min(dp[n - 1][0], dp[n - 2][1]) + map[n][2]

 

마지막으로 이러한 세가지 점화식중 최소값을 출력하면 됩니다.

 

#include <iostream>
using namespace std;

int map[1001][3];
int dp[1001][3]; // 0 : R, 1 : G, 2 : B

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 3; j++) {
            cin>>map[i][j];
        }
    }
    
    // 초기 설정
    dp[1][0] = map[1][0];
    dp[1][1] = map[1][1];
    dp[1][2] = map[1][2];
    
    // R, G, B로 각각 끝날 때의 점화식
    for(int i = 2; i <= n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + map[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + map[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + map[i][2];
    }
    
    cout<<min(dp[n][0], min(dp[n][1], dp[n][2]));
}