[백준] 1149번: RGB거리 풀이 및 해설(C++)

문제 이미지

풀이

문제를 해석해보자, 일렬로 된 집이 있다. 그런데 양 옆집과는 같은 색이면 안되며, 색을 칠하는 비용은 집마다 색깔마다 각기 다르다. 이때 최솟값을 구하라는 문제이다.

 

많은 경우의 수를 생각해야 한다. 색깔이 3개이니 [집의 수][3] 인 이차원 배열을 만든다.

그리고 각 dp[n][m]에는 n번째 집에 m번째 색깔을 칠했을 때 나올 수 있는 최솟값을 넣는다.

dp[n][m]은 dp[n-1][m이 아닌 다른 값] 에 비용을 더하면 된다.

이전 입력된 배열들을 바탕으로 다이나믹 프로그래밍으로 풀면 된다.

하위 배열에서 입력된 값에 근거하기 때문이다.

 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n;
    int house[1001][3];
    int arr[1001][3];
    cin>>n;
    cin>>arr[0][0]>>arr[0][1]>>arr[0][2];
    house[0][0]=arr[0][0];
    house[0][1]=arr[0][1];
    house[0][2]=arr[0][2];
    for(int i=1; i<n; i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        house[i][0]=arr[i][0]+min(house[i-1][1],house[i-1][2]);
        house[i][1]=arr[i][1]+min(house[i-1][0],house[i-1][2]);
        house[i][2]=arr[i][2]+min(house[i-1][1],house[i-1][0]);
    }
   
    cout<<min({house[n-1][0],house[n-1][1],house[n-1][2]});

}

해맸던 부분

처음 이 문제를 풀때는 너무 많은 경우의 수를 생각해야 되는 것 아닌 가 싶어서 감을 잡지 못했다.

하지만 배열을 1차원 배열이 아닌 2차원 배열을 쓰고,

결국 출력되는 값이 이전 배열들에 근거한다는 사실을 발견 해 dp를 이용해 풀수 있음을 깨닫게 되었다.