백준 - 17404 RGB거리 2

문제 링크입니다 : https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

 

RGB 거리 문제랑 거의 비슷한 조건이다. 다만 첫번째 집의 색과 마지막 집의 색도 고려를 해야 한다는 점...

나는 첫번째 집의 정보를 담기 위해서 캐시에 저장을 했다.

그래서 캐시가 3차원이 됐는데, 이게 맞는 풀이인지는 잘 모르겠다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 987654321

using namespace std;

int N, first;
int arr[10000][3];
int cache[10001][3][3];
int path[10001];

int getMinCost(int pos, int previous) {
    // 기저 사례
    if(pos == N) {
        if(path[0] == path[N - 1]) return INF;
        return 0;
    }

    int& ret = cache[pos][previous][first];
    if(ret != -1) return ret;

    ret = INF;


    for(int i = 0; i < 3; i++) {
        if(previous != i) {
            path[pos] = i;
            ret = min(ret, getMinCost(pos + 1, i) + arr[pos][i]);
        }
    }

    return ret;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    memset(cache, -1, sizeof(cache));

    int ret = INF;
    for(int i = 0; i < 3; i++) {
        path[0] = i;
        first = i;
        ret = min(ret, getMinCost(1, i) + arr[0][i]);
    }
    cout << ret;
    

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~