[백준/DP] 1149 - RGB거리

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

3

26 40 83

49 60 57

13 89 99

예제 출력 1

96

 

---

내 소스

#include <algorithm>
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int n,i,j;
    int **arr;
    int **house;
    int answer;
    
    cin >> n;
    arr = new int*[n];
    house = new int*[n];
    
    for(i=0; i<n; i++){
        arr[i] = new int[3];
        house[i] = new int[3];
        for(j=0; j<3; j++){
            cin >> arr[i][j];
        }
    }
    
    if(n==0){
        cout << 0;
        return 0;
    }
    
    house[0][0] = arr[0][0];
    house[0][1] = arr[0][1];
    house[0][2] = arr[0][2];
    
    for(i=1; i<n; i++){
        house[i][0] = min(house[i-1][1] + arr[i][0], house[i-1][2] + arr[i][0]);
        house[i][1] = min(house[i-1][0] + arr[i][1], house[i-1][2] + arr[i][1]);
        house[i][2] = min(house[i-1][0] + arr[i][2], house[i-1][1] + arr[i][2]);
    }
    
    answer = min(min(house[n-1][0], house[n-1][1]), house[n-1][2]);
    cout << answer;
    return 0;
}