[Python] 백준 12869번: 뮤탈리스크

https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

1. scv는 1~3마리 이므로 3마리보다 작을 때 체력이 0인 scv를 넣어준다.

2. 최대 체력은 60이므로 60인 3차원배열을 만들어준다.

3. 체력이 음수로 내려가나 0이나 같으므로 음수로 내려가면 0으로 설정해주고 9, 3, 1을 순서를 바꾸어 dfs

를 돌려준다.

n = int(input())
scv = list(map(int, input().split()))
dp = [[[0 for _ in range(61)] for _ in range(61)] for _ in range(61)]
while len(scv) < 3:
    scv.append(0)

def dfs(x, y, z):
    if x == 0 and y == 0 and z == 0:
        return 0
    if dp[x][y][z]:
        return dp[x][y][z]
    dp[x][y][z] = 1 + min(dfs(max(x-9, 0), max(y-3, 0), max(z-1, 0)), dfs(max(x-9, 0), max(y-1, 0), max(z-3, 0)), dfs(max(x-3, 0), max(y-9, 0), max(z-1, 0)),
                          dfs(max(x-3, 0), max(y-1, 0), max(z-9, 0)), dfs(max(x-1, 0), max(y-3, 0), max(z-9, 0)), dfs(max(x-1, 0), max(y-9, 0), max(z-3, 0)))
    return dp[x][y][z]

print(dfs(scv[0], scv[1], scv[2]))