[동적 계획법 1] [C++] 1149번. RGB 거리

www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

입력

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

출력

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

---

해결 방법

이 문제의 시간 제한은 0.5초로 짧다.

중첩 반복문을 이용한 브루트 포스의 방법으론 통과할 수 없다는 의미이다.

dp로 문제를 해결하기 위해선 점화식, 즉 규칙을 찾아내야한다.

 

입력 값으로 행은 2 ~ 1000까지 최대 999개의 행이 주어지고,

열은 0, 1, 2로 총 3개의 열이 주어진다.

 

이 문제의 핵심은 행의 최소 값을 다음 행의 원소와 더하되 열이 같지 않은 원소에 더해야 한다는 것이다.

 

입력 값이 저장된 배열을 house라고 했을 때

이를 점화식으로 구현하면

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

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

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

가 된다.

 

위 과정을 모든 행에 대해서 반복하면 마지막 행에는 각 열에서의 최소값들이 담겨 있다.

이 값들 중에서 가장 작은 값을 출력하면 정답.

 

 

해결 과정

점화식을 코드로 구현하고 마지막 행에서 최소값을 찾는 코드를 추가한다.

 

최종 코드는

 

#include <iostream>
using namespace std;

int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int n, a, b, c, result;
    int house[999][3];
    int dp[999][3];
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> a >> b >> c;
        house[i][0] = a;
        house[i][1] = b;
        house[i][2] = c;
    }
    
    dp[0][0] = house[0][0];
    dp[0][1] = house[0][1];
    dp[0][2] = house[0][2];
    
    for(int i = 1; i < n; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2];
    }
    
    result = dp[n-1][0];
    for(int i = 1; i < 3; i++){
        if (result > dp[n-1][i]){
            result = dp[n-1][i];
        }
    }
    
    cout << result;
    
    return 0;
}

 

min 함수는 더 작은 값을 return 해주는 함수이다.