(백준 C++)1149 RGB 거리

문제

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

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

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

입력

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

출력

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

 

 

 

 

DP 문제.

우선 house와 dp 벡터 변수를 선언한다.

house 벡터 변수는 각 집마다 RGB의 비용이 저장된다.

dp 벡터 변수는 이전, 다음집과 색이 같지 않으면서 최소 비용을 저장하는 테이블이다.

 

맨 처음 시작하는 집은 이전 집이 없기 때문에 비교를 할 필요가 없다.

때문에 dp[0]은 house[0]으로 값을 지정하고 시작하면 된다.

 

이후 점화식을 생각해보자.

현재 집의 인덱스는 1보다 크다.

그리고 R,G,B 3개의 종류마다 이전 집과 다른 색의 비용을 더해서 비용이 적게 들어가는 색을 골라야 한다.

다음 집은 생각할 필요가 없다.

왜냐하면 현재 집과 이전 집에서 색이 같지 않은 경우만 계산하면 다음 집에서도 색이 같지 않은 경우를 자동적으로 계산하게 되기 때문이다.

현재 집과 이전 집이 같은 색을 고른다는 것은 결국 house에서 행만 다를 뿐 열이 같다는 뜻이다.

즉, house[i][j]와 house[i - 1][j]는 같은 색이다.

 

그렇다면 열이 다르다는 조건을 걸면 다음과 같은 식을 구할 수 있다.

 

dp[i][j] = min(dp[i][j], dp[i - 1][k] + house[i][j]).

i = 현재 집의 인덱스(i >= 1)

j = R, G, B를 나타내는 인덱스(0 <= j <= 2)

k = 이전 집의 R, G, B를 나타내는 인덱스(0 <= k <= 2)

여기서 j와 k가 같지 않은 경우만 dp 테이블을 계산하면 된다.

 

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

using namespace std;

int main(void){
    int N, ans = 0;

    cin >> N;

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

    //dp 테이블의 0번째 값을 house의 0번째 값으로 대입
    dp[0] = house[0];

    //현재 집과 이전, 다음 집의 색이 같지 않은 경우는 각 집의 인덱스가 같지 않다는 뜻.
    //그 경우를 제외하고 더 작은 비용을 저장.
    for(int i = 1; i < N; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 3; k++){
                if(j != k){
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + house[i][j]);
                }
            }
        }
    }

    ans = min(dp[N - 1][0], min(dp[N - 1][1], dp[N - 1][2]));
    cout << ans;
    
    return 0;
}