[C++] 백준(BAEKJOON) 1149

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n;
int cost[1001][3];
int cache[1001][3];
 
int dp(int home_index, int color_index)
{
    if(home_index >= n)
        return 0;
 
    if(cache[home_index][color_index])
        return cache[home_index][color_index];
 
    int m = -1;
 
    for(int i=0;i<3;i++)
        if(i != color_index)
        {
            if( m == -1 )
                m = cost[home_index][color_index] + dp(home_index + 1, i);
            else
                m = min(m, cost[home_index][color_index] + dp(home_index + 1, i));
        }
 
    cache[home_index][color_index] = m;
    
    return m;
}

int main()
{
    scanf("%d", &n);
 
    for(int i=0;i<n;i++)
    {
        scanf("%d", &cost[i][0]);
        scanf("%d", &cost[i][1]);
        scanf("%d", &cost[i][2]);
    }
 
    int m = dp(0, 0);
    m = min(m, dp(0, 1));
    m = min(m, dp(0, 2));
 
    printf("%d", m);
 
    return 0;
}