BOJ) 12869 - 뮤탈리스크

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

12869번: 뮤탈리스크

메모이제이션을 활용해 DP로 풀이하였습니다.

---

C++ 소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
int cache[61][61][61];
int dp(int s1, int s2, int s3){
    if (s1 <0) return dp(0,s2,s3);
    if (s2 <0) return dp(s1,0,s3);
    if (s3 < 0) return dp(s1,s2,0);
    if(s1 ==0 && s2 ==0 && s3==0) return 0;
    if(cache[s1][s2][s3]!=-1) return cache[s1][s2][s3];
    int t[] = {1,3,9};
    int ret = -1;
    do {
        int tmp = dp(s1-t[0], s2-t[1], s3-t[2])+1;
        if (ret == -1 || ret > tmp) ret = tmp;
    }while(next_permutation(t,t+3));

    return cache[s1][s2][s3] = ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    fill(&cache[0][0][0], &cache[60][60][60]+1,-1);
    int scv[3] = {0,0,0};
    for(int i=0;i<n;i++){
        cin >> scv[i];
    }
    cout << dp(scv[0], scv[1], scv[2]) << '\n';
    return 0;
}