[백준 1149번] [동적 계획법] RGB 거리

i번째까지의 집을 칠하기 위한 비용을 구하기 위해서는 

i - 1번째 집의 색칠 상태가 필요하다

 

즉, 

dp[i][0~3] = i번째 index까지 칠했을 때 필요한 비용 (단, i번쨰 index를 칠한 색이 0이면 R, 1이면 G, 2이면 B)

따라서 점화식을 세워보면 구하고자 하는 답을 간단하게 구할 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int dp[1001][3];

int main(void){
    fastio;
    memset(dp, 0, sizeof(dp));

    int n;
    cin >> n;
    cin >> dp[0][0] >> dp[0][1] >> dp[0][2];

    for(int i = 1; i < n; i++){
        int r_cost, g_cost, b_cost;
        cin >> r_cost >> g_cost >> b_cost;
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r_cost;
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g_cost;
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b_cost;
    }

    cout << min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]) << "\n";

    return 0;
}