Baekjoon 1149번 RGB거리

문제

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

걸린 시간

02 : 54 : 56

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int cost[1001][4];
int cache[1001][4];

int dp(int house, int color){
    // 기저 사례
    if(house == n)
        return cost[house][color];
    // 메모이제이션
    int& ret = cache[house][color];
    if(ret != -1)
        return ret;
    // 재귀 호출
    int rgb[4]; 
    memset(rgb, 1, sizeof(rgb));
    if(color)
        rgb[color] = 0;
    int ans = INF;
    for(int i = 1; i <= 3; i++)
        if(rgb[i])
            ans = min(ans, dp(house+1, i)+cost[house][color]);
    return ret = ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> cost[i][1] >> cost[i][2] >> cost[i][3];
    memset(cache, -1, sizeof(cache));
    cout << dp(0, 0) << "\n";
    return 0;
}

문제를 잘못 이해하는 바람에 중복된 부분을 찾지 못해 그리디로 접근했었던 dp 문제.