[파이썬] 백준 12869 : 뮤탈리스크 (골드4)

[파이썬] 백준 12869 : 뮤탈리스크 (골드4)

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

---

풀이

방향성 생각

• 바텀업보다는 탑다운이 짜기 더 쉬워보인다.

---

전체코드

import sys
sys.setrecursionlimit(10**6)

N = int(input())
HP = list(map(int,input().split()))
for _ in range(3-N):
    HP.append(0)

dp = {}
def dfs(a,b,c):

    # 재방문
    if (a,b,c) in dp:
        return dp[(a,b,c)]

    # 탈출조건
    if (a,b,c) == (0,0,0):
        return 0

    answer = min(dfs(max(a-9,0),max(b-3,0),max(c-1,0)),
                 dfs(max(a-9,0),max(b-1,0),max(c-3,0)),
                 dfs(max(a-3,0),max(b-9,0),max(c-1,0)),
                 dfs(max(a-3,0),max(b-1,0),max(c-9,0)),
                 dfs(max(a-1,0),max(b-9,0),max(c-3,0)),
                 dfs(max(a-1,0),max(b-3,0),max(c-9,0))) + 1

    dp[(a,b,c)] = answer
    return answer

print(dfs(*HP))

코멘트

• 한 공격에서 한 scv 동시타격 안되는 조건을 못봐서 조건도 자세하게 적었는데 필요 없었다...
• 뮤탈은 뮤리...