[백준 12869번] 뮤탈리스크 (C++)

문제링크 : https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int scv[3];
int dp[61][61][61];

int dfs(int x, int y, int z)
{
    //파괴된 scv가 존재하면 해당 scv는 0으로
    if(x<0) return dfs(0, y, z); 
    if(y<0) return dfs(x, 0, z);
    if(z<0) return dfs(x, y, 0);

    if(x==0 && y==0 && z==0) return 0; //모두 파괴
    if(dp[x][y][z]) return dp[x][y][z]; //이미 구한값이 있다면 return

    dp[x][y][z]=MAX;
    //경우의 수 6가지
    dp[x][y][z] = min(dp[x][y][z], dfs(x - 9, y - 3, z - 1) + 1);
	dp[x][y][z] = min(dp[x][y][z], dfs(x - 9, y - 1, z - 3) + 1);
	dp[x][y][z] = min(dp[x][y][z], dfs(x - 3, y - 9, z - 1) + 1);
    dp[x][y][z] = min(dp[x][y][z], dfs(x - 3, y - 1, z - 9) + 1);
	dp[x][y][z] = min(dp[x][y][z], dfs(x - 1, y - 9, z - 3) + 1);
	dp[x][y][z] = min(dp[x][y][z], dfs(x - 1, y - 3, z - 9) + 1);

    return dp[x][y][z];
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    
    for(int i=0; i<N; i++)
    {
        cin >> scv[i];
    }
    
    cout << dfs(scv[0], scv[1], scv[2]);
    return 0;
}

 

아래와 같이 올 수 있는 경우의 수가 6가지이다.

9 3 1
9 1 3
3 9 1
3 1 9
1 9 3
1 3 9

 

이를 이용하여 직전 위 경우의 수 + 1과 현재 dp 값 중에서 작은 값을 계쏙해서 담으며 갱신해준다.

추가적으로 특정 scv만 파괴되는 경우가 발생하는데 이는 x, y, z의 각 값이 0 미만일 때 바로 0으로 대체하여 대신 넣어주는 예외처리를 해준다.

 

이렇게 x, y, z가 모두 0이 된다면 모두 파괴를 성공한 것이기에 탐색을 종료하고, 탐색 도중 현재 dp에 값이 이미 있다면 전에 계산을 이미 해놓은 것이므로 중복을 줄이기 위해 현재 dp값을 바로 return 해준다.