백준 1149번 RGB거리

백준 1149번 RGB거리

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
 
int arr[1001][1001];
int cache[1001][1001];
 
int n;
int Paint(int y,int x ) {
 
    if (y == n - 1) return arr[y][x];
 
    int &ret = cache[y][x];
 
    if (ret != -1) return ret;
 
    if (x == 0) {
        return ret = (min(Paint(y + 1, x + 1), Paint(y + 1, x + 2)) + arr[y][x]);
    }
    else if (x == 1) {
        return ret = (min(Paint(y + 1, x - 1), Paint(y + 1, x + 1)) + arr[y][x]);
    }
    else if (x == 2) {
        return ret = (min(Paint(y + 1, x - 2), Paint(y + 1, x - 1)) + arr[y][x]);
    }
}
 
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    memset(cache, -1, sizeof(cache));
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
    
    int Ret = 987654321;
    for (int i = 0; i < 3; i++) {
        Ret = min(Ret, Paint(0, i));
    }
    cout << Ret;
 
    return 0;
}

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

기본 동적계획법 문제입니다. 현재상태가 R G B인 경우 3가지를 케이스 분류해줘서 

풀어주면 쉽게 풀 수 있는 문제였습니다.