BAEKJOON 1149 - RGB거리

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

memoization을 이용한 동적 계획법으로 풀 수 있는 문제입니다. 첫 번째 집을 칠할 때는 전에 칠한 집의 색이 없으므로 모든 색을 칠할 수 있기에 rgb 값 0~2이 아닌 3을 넘겨줍니다. 

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
int cost[1000][3];
int cache[1000][4];
 
int dp(int curHouse, int preColor, int n)
{
    if (curHouse == n)
    {
        return 0;
    }
 
    int& ret = cache[curHouse][preColor];
    if (ret != -1)
    {
        return ret;
    }
 
    ret = INT_MAX;
    for (int i = 0; i < 3; i++)
    {
        if (preColor != i)
        {
            ret = min(ret, dp(curHouse + 1, i, n) + cost[curHouse][i]);
        }
    }
    return ret;
}
 
int main()
{
    memset(cache, -1, sizeof(cache));
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);
    }
 
    printf("%d\n", dp(0, 3, n));
 
    return 0;
}