2. 백준 1149 RGB거리 문제 공부

1. 문제를 풀면서

 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 두 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다.

2. 문제 출처 및 보기

 https://www.acmicpc.net/problem/1149

3. 문제 해결

 이 문제는 동적 계획법을 처음 풀어보면 어려울 수 있다. 해결 방법은 이렇다. RGB 색상을 칠하면서 집을 옮겨다녀야 한다. 그리고 반드시 첫 집에서 R, G, B 중 하나를 선택해야 한다. 첫집은 물론이고 다음 집으로 가면서 무엇을 선택해야 할지는 아직 모른다. 그러므로 현재 집에서 각각의 색상을 선택했을 때, 이전 집까지의 최소 값과 더하여 현재 집에서 최소가 될 수 있는 색상을 찾아야 한다. 이 때 신경 쓸 부분은 색상을 연속으로 칠할 수 없다는 조건이 있으므로, 현재 집에서 R을 칠하고자 한다면 이전 집이 G나 B가 선택됐을 때의 누적된 비용과 더해준다. 그렇게 현재 집에서 각각의 색상을 선택했을 때의 최소 비용을 구할 수 있다. 그 중 최소 누적 비용이 정답이 될 것이다.

4. 내 소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int len = 0;
    int house_cost[1000][3];
    int result[1000][3];
 
    // 비용 데이터 입력 및 저장
    scanf("%d", &len);
    for (int idx = 0; idx < len; idx++) {
        int r, g, b;
        scanf("%d %d %d", &r, &g, &b);
        house_cost[idx][0] = r;
        house_cost[idx][1] = g;
        house_cost[idx][2] = b;
    }
 
    // 첫 인덱스에 누적 비용 세팅
    result[0][0] = house_cost[0][0];
    result[0][1] = house_cost[0][1];
    result[0][2] = house_cost[0][2];
 
 
    // 문제 해결 : 누적 비용 계산
    for (int idx = 1; idx < len; idx++)
    {
        for (int col = 0; col < 3; col++)
        {
            if (col == 0) { // 현재 집에서 R을 선택한다면.. 누적 값은? 
                result[idx][col] = house_cost[idx][col] + min(result[idx - 1][1], result[idx - 1][2]);
            }
            else if (col == 1) { // 현재 집에서 G를 선택한다면.. 누적 값은? 
                result[idx][col] = house_cost[idx][col] + min(result[idx - 1][0], result[idx - 1][2]);
            }
            else if (col == 2) { // 현재 집에서 B를 선택한다면.. 누적 값은? 
                result[idx][col] = house_cost[idx][col] + min(result[idx - 1][0], result[idx - 1][1]);
            }
        }
    }
 
    // 결과 출력 : 최소 값 출력
    int answer = result[len - 1][0] < result[len - 1][1] ? min(result[len - 1][0], result[len - 1][2]) : min(result[len - 1][1], result[len - 1][2]);
    printf("%d\n", answer);
 
    return 0;
}