RGB거리 2

백준 17404번: RGB거리 2

아이디어

Cache[이전에 칠한 색][현재 집 번호] 에 메모이제이션 ㄱㄱ

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1000][3];
int cache[4][1000];

int solve(int start, int rgb, int cur) {
    if (cur == N) {
        if (rgb == start) return -1;
        else return 0;
    }
    
    int& ret = cache[rgb][cur];
    if (ret != -1) return ret;
    
    ret = 10000000;
    for (int i = 0; i < 3; i++) {
        if (rgb == i) continue;
        int x = solve(start, i, cur+1);
        if (x != -1) {
            ret = min(ret, x + arr[cur][i]);
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[i][j];
        }
    }
    int ans = INT_MAX;
    for (int i = 0; i < 3; i++) {
        memset(cache, -1, sizeof(cache));
        ans = min(ans, solve(i, i, 1) + arr[0][i]);
    }
    cout << ans;
    return 0;
}

여담

시작 색이랑 마지막 색이랑 비교 ㄱㄱ