[알고리즘/백준] 12869번 : 뮤탈리스크(python)

dp를 3차원 리스트로 만들어서 풀었다. 61개를 만들지 않고 받는 체력중에 가장 큰 체력으로 리스트를 만듦...

permutations를 사용하여 9, 3, 1을 조합했다. 계속해서 빼다가 세 수가 0이하로 내려가면 return을 해줌...

만약 scv가 3마리가 아니면 빈 칸에 0을 넣어서 3으로 맞춰준다.

from itertools import permutations


def answer(x, y, z, cnt):
    global ans
    if x <= 0 and y <= 0 and z <= 0:
        if ans > cnt:
            ans = cnt
            return

    x = 0 if x <= 0 else x
    y = 0 if y <= 0 else y
    z = 0 if z <= 0 else z

    if dp[x][y][z] <= cnt and dp[x][y][z] != 0:
        return

    dp[x][y][z] = cnt

    for i in permutations([9, 3, 1], 3):
        answer(x - i[0], y - i[1], z - i[2], cnt + 1)


N = int(input())
a = list(map(int, input().split()))
while len(a) < 3:
    a += [0]
ans = 100
dp = [[[100] * (max(a) + 1) for i in range((max(a) + 1))] for j in range((max(a) + 1))]
answer(a[0], a[1], a[2], 0)
print(ans)