https://www.acmicpc.net/board/view/44639
남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
처음에는 뮤탈?? 이게 뭐지??하고 조금 고민이 됐지만, 작은 문제로 쪼개서 풀 수 있음을 깨닫고 점화식을 세워 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]))