[Algorithm]Baekjoon 12869번 : 뮤탈리스크

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

12869번: 뮤탈리스크

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
int n;
int scvHPArr[3] = { 0 };
int dp[61][61][61] = { 0 };
int attacksInfo[6][3] = { {9,3,1}, {9,1,3}, {3,9,1}, {3,1,9}, {1,9,3}, {1,3,9} };
 
 
int dfs(int firstHP, int secondHP, int thirdHP)
{
    if (firstHP <= 0 && secondHP <= 0 && thirdHP <= 0)
    {
        return 0;
    }
 
    firstHP = max(firstHP, 0);
    secondHP = max(secondHP, 0);
    thirdHP = max(thirdHP, 0);
 
    if (dp[firstHP][secondHP][thirdHP] > 0) return dp[firstHP][secondHP][thirdHP];
 
    dp[firstHP][secondHP][thirdHP] = 60;
 
    for (int i = 0; i < 6; ++i)
    {
        dp[firstHP][secondHP][thirdHP] = min(dp[firstHP][secondHP][thirdHP], dfs(firstHP - attacksInfo[i][0], secondHP - attacksInfo[i][1], thirdHP - attacksInfo[i][2]) + 1);
    }
 
    return dp[firstHP][secondHP][thirdHP];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> scvHPArr[i];
    }
 
    cout << dfs(scvHPArr[0], scvHPArr[1], scvHPArr[2]);
 
}

 

최소의 공격횟수로 최대 3개의 scv의 체력을 0으로 만들어야 하는 문제이다.

모든경우를 따지면서 재귀를 반복하면서 최소값을 기록해주면 되는데, 유의해야할 점은 체력을 깎다가보면 음수가 될 수 있다. 배열의 음수인덱스에 접근하면 터지기 때문에 음수일경우 0으로 조정해주는 코드를 작성해줘야 한다.

 

위 코드처럼 주어진 체력에서 깎아내려도 되고, 0부터시작해서 데미지를 누적하다가 scv체력들을 넘었을 때 끝내도 된다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
int n;
int scvHPs[3] = { 0 };
int dp[71][71][71] = { 0 };
int attacksInfo[6][3] = { {9,3,1}, {9,1,3}, {3,9,1}, {3,1,9}, {1,9,3}, {1,3,9} };
 
int dfs(int firstHP, int secondHP, int thirdHP)
{
    if (firstHP >= scvHPs[0] && secondHP >= scvHPs[1] && thirdHP >= scvHPs[2])
    {
        return 0;
    }
 
    firstHP = min(firstHP, scvHPs[0]);
    secondHP = min(secondHP, scvHPs[1]);
    thirdHP = min(thirdHP, scvHPs[2]);
 
    if (dp[firstHP][secondHP][thirdHP] > 0) return dp[firstHP][secondHP][thirdHP];
 
    dp[firstHP][secondHP][thirdHP] = 60;
 
    for (int i = 0; i < 6; ++i)
    {
        int nextFirstHP = firstHP + attacksInfo[i][0];
        int nextSecondHP = secondHP + attacksInfo[i][1];
        int nextThirdHP = thirdHP + attacksInfo[i][2];
 
        dp[firstHP][secondHP][thirdHP] = min(dp[firstHP][secondHP][thirdHP], dfs(nextFirstHP, nextSecondHP, nextThirdHP) + 1);
    }
 
    return dp[firstHP][secondHP][thirdHP];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> scvHPs[i];
    }
 
    cout << dfs(0, 0, 0);
}