1149번 : RGB거리

Backjoon Online Judge 

"1149번 : 피보나치 수 3" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/1149

일단 문제에서 비용의 최솟값을 출력하기 위해 모든 선택 경우에서 나올 수 있는 비용을 알고 있어야 하고, 이를 구현하기 위해 DP를 이용하였습니다.

이때 문제의 조건을 만족하려면 현재 집을 칠해야 할 색은 이전집에 칠한 색깔이 아닌 색만을 칠할 수 있다는 사실을 확인했고 배열을 통해 검사하는 범위를 줄이기로 했습니다.

 - 먼저 N <= 1000이므로 모든 집의 색깔을 저장할 3*1000의 배열을 선언하여 그 배열에 저장하였습니다.

 - 이후 N에 따라 검사 결과를 저장할 total 배열에 비용의 최솟값을 저장했습니다. 이때 비용의 최솟값을 저장하기 위해 algorithm헤더에 포함된 min함수를 이용하였습니다.

 - 비용은 현재 집에 칠할 색깔 별로 비용을 각각 구했으며 비용은 이전 집에 칠한 색깔의 최솟값 중 현재 집에 칠할 색깔과 같지 않은 최솟값 중 작은것을 더했습니다.

코드는 C++로 작성하였습니다.

#include <iostream>
#include <algorithm>
 
#define MAX 1000
 
using namespace std;
 
int main() {
    int N, miniMum;
    int cost[MAX][3] = { 0 };
    int total[MAX][3] = { 0 };
 
    cin >> N;
 
    for(int i = 0; i < N; i++) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }
 
    total[0][0] = cost[0][0];
    total[0][1] = cost[0][1];
    total[0][2] = cost[0][2];
 
    for (int i = 1; i < N; i++) {
        total[i][0] = cost[i][0] + min(total[i - 1][1], total[i - 1][2]);
        total[i][1] = cost[i][1] + min(total[i - 1][0], total[i - 1][2]);
        total[i][2] = cost[i][2] + min(total[i - 1][0], total[i - 1][1]);
    }
 
    cout << min(total[N - 1][0], min(total[N - 1][1], total[N - 1][2]));
    return 0;
}