[백준 1149번] RGB거리 C++

www.acmicpc.net/problem/1149

1149번: RGB거리

탑다운방식으로 풀려다 도저히 힘들어서

바텀업 방식으로 풀었다.

 

만약 dp(n)이 n번쨰 집까지 쓴 cost라면

dp(n) = cost(n)+min(dp(n-1,안쓴색),dp(n-1,안쓴색))

이렇게 점화식을 세웠다

 

탑다운으로 풀다 머리빠질뻔

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
//두번째 idx 가 0=빨 1=초 2=파
int cost[1001][3];
int dp[1001][3];
 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> cost[i][j];
 
    for (int i = 1; i <= n; i++) {
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = cost[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;
}