#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int idx[6][3] = {{9, 3, 1}, {9, 1, 3}, {3, 1, 9}, {3, 9, 1}, {1, 3, 9}, {1, 9, 3}};
int dp[61][61][61];
int scv[3];
int count = 0;
int idx2[2][2] = {{9, 3}, {3, 9}};
int go(int scv1, int scv2, int scv3)
{
    if (scv1 < 0)
        return go(0, scv2, scv3);
    if (scv2 < 0)
        return go(scv1, 0, scv3);
    if (scv3 < 0)
        return go(scv1, scv2, 0);
    if (scv1 == 0 && scv2 == 0 && scv3 == 0)
        return 0;
    if (dp[scv1][scv2][scv3] != -1)
        return dp[scv1][scv2][scv3];
    int ans = 100001;
    for (int i = 0; i < 6; i++)
    {
        if (ans > go(scv1 - idx[i][0], scv2 - idx[i][1], scv3 - idx[i][2]))
        {
            ans = go(scv1 - idx[i][0], scv2 - idx[i][1], scv3 - idx[i][2]);
        }
    }
    ans += 1;
    dp[scv1][scv2][scv3] = ans;
    return (dp[scv1][scv2][scv3]);
}
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i <= 60; i++)
    {
        for (int j = 0; j <= 60; j++)
        {
            for (int k = 0; k <= 60; k++)
            {
                dp[i][j][k] = -1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        cin >> scv[i];
    }
    cout << go(scv[0], scv[1], scv[2]) << "\n";

    return 0;
}

문제 접근

다이나믹으로 접근.

해결 방법

dp[i][j][k] = scv 가 i 체력이 있고, scv 두번째가 j 체력이 있고, scv 세번째가 k 체력이 있을 때 공격해야 하는 최소 값.
이는
1,3,9 dp[i-1][j-3][k-9] + 1;
1,9,3 dp[i-1][j-3][k-9] + 1;
3,1,9 dp[i-3][j-1][k-9] + 1;
3,9,1 dp[i-3][j-9][k-1] + 1;
9,1,3 dp[i-9][j-1][k-3] + 1;
9,3,1 dp[i-9][j-3][k-1] + 1;
총 6가지 방법으로 나타낼 수 있다.

시간 복잡도는 체력이 a , scv 의 개수를 n 이라고 할 때 (a+1) ^n (n!) 이다.

의문점 및 헷갈린 점

재귀함수를 이용하여 다이나믹 방식을 적용한다. 처음에 1,2,3 가지일때의 경우를 나누어야 하나 생각을 했었는데, 그리고 dp의 배열에 {1,3,9} 원소가 빼져서 음수값인 범위를 참조하는 것을 어떻게 막지 고민을 했었는데, 재귀함수를 이용하여 , 만약 음수라면 0을 넣어주고 다시 재귀함수를 호출하는 방식으로 해결할 수 있었다. 이 점이 가장 어려웠던 점이 었던것 같다.