백준 12869번 뮤탈리스크 C++

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

12869번: 뮤탈리스크

 

dp

 

#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;

vector<int> v;
vector<vector<vector<int>>> cache;

int dfs(int a, int b, int c) {
    if (a < 0) a = 0;
    if (b < 0) b = 0;
    if (c < 0) c = 0;

    int& val = cache[a][b][c];
    if (val != -1) return val;
    val = INT_MAX;

    val = min(val, dfs(a - 9, b - 3, c - 1) + 1);
    val = min(val, dfs(a - 9, b - 1, c - 3) + 1);

    val = min(val, dfs(a - 1, b - 9, c - 3) + 1);
    val = min(val, dfs(a - 3, b - 9, c - 1) + 1);

    val = min(val, dfs(a - 3, b - 1, c - 9) + 1);
    val = min(val, dfs(a - 1, b - 3, c - 9) + 1);

    return val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    v = vector<int>(3, 0);
    for (int i = 0; i < n; i++) cin >> v[i];
    cache = vector<vector<vector<int>>>(61, vector<vector<int>>(61, vector<int>(61, -1)));
    cache[0][0][0] = 0;

    cout << dfs(v[0], v[1], v[2]);
}