이번 문제는 DP와 permutations를 사용하여 풀이하였다. 처음에는 패턴을 찾아보려고 했지만 공격의 최대 횟수가 3이기 때문에 permutations를 사용해도 크게 성능에 지장이 없을 것 같아 permutations으로 공격 순서의 모든 경우를 비교하며 dp[a][b][c]를 최솟값으로 갱신하였다.

• n을 입력받는다.
• scv를 입력받는다.
• 만약 n이 3보다 작을 경우,
  -> scv에 [0]을 3-n 만큼 더한다. (인덱스 에러 방지)
• 공격 순서에 따른 공격력을 저장할 리스트 attacks를 [9, 3, 1]로 선언한다.
• 각 체력에 따른 공격 횟수를 저장할 리스트 dp를 61*61*61의 크기로 선언하고 -1을 채운다.
• hp_update 함수를 a, b, c를 인자로 갖도록 선언한다.
  -> 만약 a가 0보다 작을 경우,
  --> hp_update(0, b, c)를 반환한다.
  -> 만약 b가 0보다 작을 경우,
  --> hp_update(a, 0, c)를 반환한다.
  -> 만약 c가 0보다 작을 경우,
  --> hp_update(a, b, 0)을 반환한다.
  -> 만약 a, b, c가 모두 0일 경우, 0을 반환한다.
  -> 만약 dp[a][b][c]가 -1이 아닌 경우,
  --> dp[a][b][c]를 반환한다.
  -> dp[a][b][c]를 최댓값으로 갱신한다.
  -> attacks의 permutations 리스트를 순회하는 damage에 대한 for문을 돌린다.
  --> dp[a][b][c]를 dp[a][b][c]와 hp_update(a-damage[0], b-damage[1], c-damage[2]) 중 더 작은 값으로 갱신한다.
  -> dp[a][b][c]를 1 증가시킨다.
  -> dp[a][b][c]를 반환한다.
• hp_update(scv[0], scv[1], scv[2])를 출력한다.

Code

import itertools
import sys
n=int(input())
scv=list(map(int, input().split()))
if n<3:
    scv+=[0]*(3-n)
attacks=[9, 3, 1]
dp=[[[-1 for _ in range(61)] for _ in range(61)] for _ in range(61)]
def hp_update(a, b, c):
    if a<0:
        return hp_update(0, b, c)
    if b<0:
        return hp_update(a, 0, c)
    if c<0:
        return hp_update(a, b, 0)
    if not a and not b and not c:
        return 0
    if dp[a][b][c]!=-1:
        return dp[a][b][c]
    dp[a][b][c]=sys.maxsize
    for damage in list(itertools.permutations(attacks)):
        dp[a][b][c]=min(dp[a][b][c], hp_update(a-damage[0], b-damage[1], c-damage[2]))
    dp[a][b][c]+=1
    return dp[a][b][c]
print(hp_update(scv[0], scv[1], scv[2]))