백준 12869 뮤탈리스크

 

간단한 해설

 

뮤탈 타다당을 얼마나 효율적으로 쏠 지 계산하는 문제

 

n이 최대 3이고 최대 체력이 60이니까 단순한 bfs로 해결할 수도 있다고 생각할 수 있으나, 방문 처리를 안해주면 방문한 곳을 재방문해서 시간초과가 일어날 수 있음을 명시해야 한다.

 

재방문처리를 생각하면 문제 유형은 dp+bfs라 생각해도 된다.

 

코드를 좀 더 간결하게 짤 수도 있었지만 그냥 문제풀이가 목적이므로 같은 부분을 반복해서 복붙했다.

 

헷갈리지 않도록 주석 쓴게 포인트

답

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dp[61][61][61];
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    fill(&dp[0][0][0],&dp[60][60][61],987654321);
    vector<int> v(3,0);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    priority_queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push({{0,v[0]},{v[1],v[2]}});
    while(!q.empty()){
        int time=-q.top().first.first;
        int a=q.top().first.second;
        int b=q.top().second.first;
        int c=q.top().second.second;
        q.pop();
        if(a==0&&b==0&&c==0){
            dp[0][0][0]=time;
            break;
        }
        vector<int> tmp(3,0);
        int nxtTime=time+1;
        // 9 3 1
        tmp[0]=max(a-9,0);
        tmp[1]=max(b-3,0);
        tmp[2]=max(c-1,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
        // 9 1 3
        tmp[0]=max(a-9,0);
        tmp[1]=max(b-1,0);
        tmp[2]=max(c-3,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
        // 3 9 1
        tmp[0]=max(a-3,0);
        tmp[1]=max(b-9,0);
        tmp[2]=max(c-1,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
        // 3 1 9
        tmp[0]=max(a-3,0);
        tmp[1]=max(b-1,0);
        tmp[2]=max(c-9,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
        // 1 3 9
        tmp[0]=max(a-1,0);
        tmp[1]=max(b-3,0);
        tmp[2]=max(c-9,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
        // 1 9 3
        tmp[0]=max(a-1,0);
        tmp[1]=max(b-9,0);
        tmp[2]=max(c-3,0);
        sort(tmp.begin(),tmp.end());
        if(dp[tmp[0]][tmp[1]][tmp[2]]>nxtTime){
            dp[tmp[0]][tmp[1]][tmp[2]]=nxtTime;
            q.push({{-nxtTime,tmp[0]},{tmp[1],tmp[2]}});
        }
    }
    cout<<dp[0][0][0];
}