백준 17404번 RGB거리 2 C++

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

17404번: RGB거리 2

 

첫번째 집을 빨강, 초록, 파랑 색으로 각각 지을 때 최솟값을 찾고 셋중에서 최솟값을 찾았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;

const int CNT = 3;

vector<vector<int>> cost;
vector<vector<int>> cache;

int dfs(int loc, int color, int firstColor) {
    int& val = cache[loc][color];
    if (loc == n - 1) {
        if (color == firstColor) return val = INT_MAX;
        return val = cost[loc][color];
    }
    if (val != -1) return val;
    val = 0;
    return val = cost[loc][color] + min(dfs(loc + 1, (color + 1) % CNT, firstColor), dfs(loc + 1, (color + 2) % CNT, firstColor));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    cin >> n;
    cost = vector<vector<int>>(n, vector<int>(CNT));
    cache = vector<vector<int>>(n, vector<int>(CNT, -1));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < CNT; j++) {
            cin >> cost[i][j];
        }
    }

    int ans1 = dfs(0, 0, 0);
    cache = vector<vector<int>>(n, vector<int>(CNT, -1));
    int ans2 = dfs(0, 1, 1);
    cache = vector<vector<int>>(n, vector<int>(CNT, -1));
    int ans3 = dfs(0, 2, 2);

    int ans = min(ans1, min(ans2, ans3));
    cout << ans;
}