백준, BOJ, 12869번, 뮤탈리스크 C++ [CPP] ★★★★

DFS + DP 문제다.

나는.. DP를 까먹고 있어서 답을 결국 봐버렸다.ㅠㅠ

어쩐지.. 이 문제는 중요해보였다.

아니 우선 나에게 통찰력을 주었다.

https://www.acmicpc.net/submit/12869/48753292

 

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


//재귀만 해보려는데 도저히 생각이 안나서...답을 찾았다.
int dp[61][61][61]; //DP를 사용하라는데.. 재귀 + DP란다.


//scv 체력 a,b,c에 대해서 각 공격을 적용해본다.
int func(int a, int b, int c){
    //죽은 scv에 대해서는 연산하지 않는다.
    //이 처리를 하는 이유는 음수에 대한 계산을 하지 않기 때문이다.
    if(a<0)return func(0,b,c);
    if(b<0)return func(a,0,c);
    if(c<0)return func(a,b,0);
    
    //만약 처음부터 다 파괴되어있다면 공격하지 않아도 된다 => 0번 공격
    if(a==0&&b==0&&c==0) return 0;
    
    //이미 계산했다면 바로 return 함 => 재귀가 너무 많아지는 것을 방지하는 DP + 재귀
    if(dp[a][b][c] != -1)return dp[a][b][c];
    
    //3개에 대한 공격 종류는 6가지
    dp[a][b][c]=123456789;
    //최솟값에 대해서만 dp가 가지고 있는다.
    dp[a][b][c] = min(dp[a][b][c], func(a-9,b-3,c-1)+1);
    dp[a][b][c] = min(dp[a][b][c], func(a-9,b-1,c-3)+1); 
    dp[a][b][c] = min(dp[a][b][c], func(a-3,b-9,c-1)+1); 
    dp[a][b][c] = min(dp[a][b][c], func(a-3,b-1,c-9)+1); 
    dp[a][b][c] = min(dp[a][b][c], func(a-1,b-3,c-9)+1); 
    dp[a][b][c] = min(dp[a][b][c], func(a-1,b-9,c-3)+1); 
    
    return dp[a][b][c];
}
    


int N;
int main(){
    cin >> N;
    
    //배열 모두 초기화
    memset(dp, -1, sizeof(dp));
    vector<int> scv;
    for(int i = 0; i<N; i++){
        int hp;
        cin >> hp;
        scv.push_back(hp);
    }
    cout << func(scv[0],scv[1],scv[2]) << '\n';
    
    
    
    return 0;
}