[DP] 백준 1149번 - RGB 거리

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

1149번: RGB거리

백준 DP 연습문제다.

입력받은 각 위치의 RGB값을 갖고 이전에 합산해둔 (메모이제이션) 최소 RGB 비용을 비교해 더 작은 비용값에 더해주며 최종 N의 자리까지 가면된다. N의 자리까지 가면 세 색깔에 대한 값을 모두 비교해주어 그 중 가장 작은 값을 답으로 출력하면 된다.

 

#include <iostream>
#include <algorithm>
#define maxlen 1001
using namespace std;
int DP[maxlen][3];
int N;
int main(){
    cin >> N;
    DP[0][0] = DP[0][1] = DP[0][2] = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 0; j < 3; j++){
            cin >> DP[i][j];
        }
        DP[i][0] += min(DP[i - 1][1], DP[i - 1][2]);
        DP[i][1] += min(DP[i - 1][0], DP[i - 1][2]);
        DP[i][2] += min(DP[i - 1][0], DP[i - 1][1]);
    }
    cout << min(DP[N][0], min(DP[N][1], DP[N][2]));
    return 0;
}