알고리즘/Dynamic Programming
[DP] 백준 12869번 : 뮤탈리스트 - 파이썬 Python
코딩균
2022. 2. 16. 13:11
https://www.acmicpc.net/problem/12869
12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
DP문제는 내가 제일 어려워하는 유형이라 이 문제는 풀지 못하였다
백준 강의 앞부분에서 힌트를 얻고 풀어본 것을 써본다
생각하기
SCV의 값은 3이하로 매우 작다
각각의 SCV는 체력을 가지고 있다.
DP[i][j][k] - SCV의 체력이 i, j, k 일때 모두 파괴하는 최소 공격횟수
SCV가 3마리라고 가정으로 하고 만약 2마리인 경우에는 DP[i][j][0]으로 처리해주면 된다
따라서 3차원 DP를 만들어놓고 시작함
공격할 수 있는 경우의 수는 총 6가지
(-9, -3, -1) (-9, -1, -3) (-3, -9, -1) (-3, -1, -9) (-1, -9, -3) (-1, -3, -9)
6가지의 공격 가능한 경우에서
DP[i][j][k] = DP[i-공격받은 hp][j-공격받은 hp][k-공격받은 hp] + 1
가장 작은 수를 DP에 넣어줌
초기값 : DP[0][0][0] = 0 / i, j, k가 모두 음수여도 DP[i][j][k] = 0
구현하기
Top-Down 방식이므로 재귀를 통해 구현
Top-Down은 함수의 호출로 구현을 하고 Bottom-Up은 DP인덱스에 접근을 통해 구현
- i, j, k가 모두 0이하인 경우 (0 혹은 음수) 0을 return
- dp[i][j][k] != -1인 경우 - 이전에 저장된 값이 있다는 이야기이므로 dp[i][j][k] return
- i, j, k가 음수인 경우에는 0으로 바꾸어서 dp에 적용
from itertools import permutations
N = int(input())
attack = [-9, -3, -1]
hp = list(map(int, input().split()))
# 공격 가능한 순열 리스트
perm = list(permutations(attack, 3))
dp = [[[-1 for k in range(61)] for j in range(61)] for i in range(61)]
def dp_cal(i, j, k):
if i<=0 and j<=0 and k<=0 :
return 0
if i<0:
ni = 0
else:
ni = i
if j<0:
nj = 0
else:
nj = j
if k<0:
nk = 0
else:
nk = k
if dp[ni][nj][nk] != -1:
return dp[ni][nj][nk]
min_num = int(1e9)
for p in perm:
result = dp_cal(ni+p[0], nj+p[1], nk+p[2]) + 1
if result < min_num:
min_num = result
dp[ni][nj][nk] = min_num
return min_num
if N==1:
print(dp_cal(hp[0], 0, 0))
elif N==2:
print(dp_cal(hp[0], hp[1], 0))
else:
print(dp_cal(hp[0], hp[1], hp[2]))