[백준 - Python] 12869 - 뮤탈리스크

0.  문제 링크

 

 

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

12869번: 뮤탈리스크

---

1.  풀이 방법

 

 

일단 9, 3, 1로 때리는 순서는 순열을 이용해서 풀었다.

점화식을 얘기하자면 scv의 피가 1, 1, 1이라고 가정했을 때, 한 대만 때려도 된다.

그러면 피가 9, 3, 1 일 때는? 이때도 한 대만 때려도 된다.

결론적으로 피 i, j, k가 있을 때는 피가 i - 9, j - 3, k - 1 때보다 한 대만 더 때리면 된다는 뜻! (물론 순열을 이용해서 모든 경우의 수를 봐야 한다.)

따라서 딕셔너리를 이용하여 특정 피 i, j, k가 될 때까지 때린 횟수는 기존의 횟수와 i - 9, j - 3, k - 1을 만들 때 때린 횟수 + 1을 하여 비교하면 된다.

그렇게 0, 0, 0부터 차곡차곡 쌓아서, 입력 받은 피가 될 때까지 for loop를 돌리면 된다.

---

2.  코드

 

 

import itertools

n = int(input())
x = y = z = 0
if n == 1:      # n이 1이라면 x만
    x = int(input())
elif n == 2:        # n이 2라면 x, y만
    x, y = map(int, input().split())
else:
    x, y, z = map(int, input().split())

dp = {(0, 0, 0) : 0}        # list 대신 딕셔너리 씀
for i in range(x + 1):
    for j in range(y + 1):
        for k in range(z + 1):
            for d_x, d_y, d_z in itertools.permutations([9, 3, 1], 3):      # 순열
                dp[(i, j, k)] = min(dp.get((i, j, k), float('inf')), dp[(max(0, i - d_x), max(0, j - d_y), max(0, k - d_z))] + 1)
                # 기존에 있는 i, j, k보다 값과 데미지를 줬을 때의 값을 비교하여 작은 걸 선택함
print(dp[(x, y, z)])

---

3.  마무리