[DP] 백준 12869번 : 뮤탈리스트 - 파이썬 Python

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

12869번: 뮤탈리스크

 

 

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]))