https://www.acmicpc.net/board/view/44639

문제 요구사항

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

문제 풀이

• 탑 다운 방식의 dp풀이
• 점화식: d[x][y][z] = min(d[x][y][z], d[x-i][y-j][z-k] + 1)
• i, j, k는 permutation(9,3,1)

처음에는 뮤탈?? 이게 뭐지??하고 조금 고민이 됐지만, 작은 문제로 쪼개서 풀 수 있음을 깨닫고 점화식을 세워 dp방식으로 풀었다:D
갑자기 스타가 하고 싶어진다... (제가 뮤컨 좀 치거든요??)

from itertools import permutations

def dfs(x, y, z):
    if x <= 0 and y <= 0 and z <= 0:
        return 0

    if x < 0: x = 0
    if y < 0: y = 0
    if z < 0: z = 0
    if d[x][y][z] < 1000: return d[x][y][z]

    for i, j, k in list(permutations(attack)):
        d[x][y][z] = min(d[x][y][z], dfs(x - i, y - j, z - k) + 1)

    return d[x][y][z]

n = int(input())
arr = list(map(int,input().split()))
if n == 1:
    arr = arr + [0,0]
elif n == 2:
    arr = arr +[0]

attack = [9, 3, 1]
d = [[[1000]*61 for _ in range(61)] for _ in range(61)]
# d[x][y][z] = min(d[x][y][z], d[x-9][y-3][z-1] + 1)
# 1 3 9
print(dfs(arr[0], arr[1], arr[2]))