[C++] 백준 1149 - RGB거리 (DP) 풀이

백준 1149번 RGB거리 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 

문제 링크

1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

백준 1149번

알고리즘

1. cnt [1001][3]라는 이중 배열을 선언해 cnt [n][o]은 n 번째 집을 빨간색으로 칠할 때 최솟값, cnt [n][1]은 n 번째 집을 초록색으로 칠할 때 최솟값, cnt [n][2]은 n 번째 집을 파란색으로 칠할 때 최솟값으로 정한다.
2. for문을 돌면서 입력과 연산을 함께 하기 위해 범위를 1부터 n 이하로 잡았고, 맨 처음 n=1 일 때 i-1은 n이 0일 때가 되므로 위에서 이중 배열 cnt를 선언할 때 꼭 0으로 초기화시켜줘야 한다.
3. for문을 돌아가는 과정을 보자면, i번째 집을 빨간색으로 칠할경우 이전 집이 초록색이나 파란색으로 칠해져야 하므로 그중에 작은 값, min()을 활용해 구해주고 입력받은 빨간색 비용을 더해준다.
4. 이 과정을 반복하다 보면 n 번째 집이 빨간색으로 칠해졌을 때 최솟값(cnt [n][0]), 초록색으로 칠해졌을 때 최솟값(cnt [n][1]), 파란색으로 칠해졌을 때 최솟값(cnt [n][2])이 구해지므로 마지막에는 이 세 값들 중 최솟값을 출력해주면 이 값이 모든 집을 칠하는 비용의 최솟값이 되는 것이다.

 

코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;

    int cnt[1001][3]={0,};
    int rgb[4];
    for(int i=1;i<=n;i++){
        cin>>rgb[0]>>rgb[1]>>rgb[2];
        cnt[i][0]=min(cnt[i-1][1],cnt[i-1][2])+rgb[0];
        cnt[i][1]=min(cnt[i-1][0],cnt[i-1][2])+rgb[1];
        cnt[i][2]=min(cnt[i-1][0],cnt[i-1][1])+rgb[2];
    }
    cout<<min(cnt[n][0],min(cnt[n][1],cnt[n][2]));
    
    return 0;
}

 

제출 결과

점화식을 찾지못해 막힌채로 엄청 헤맸다.

알고리즘을 구하는 데 꽤나 애먹었던 문제이다. 키포인트는 매번 빨간색, 초록색, 파란색으로 칠하는 최솟값을 저장해놓고, 마지막에 그 3개를 비교하는 것에 있는 것 같다.