[코테] 백준 다이나믹 프로그래밍 12869번 문제

12869번 : 뮤탈리스크

문제 링크

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

문제 설명

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

문제풀이

(0,0,0) ~ [s,c,v] 값까지 반복하면서 9,3,1의 순열을 받아 s,c,v가 해당 데미지를 받을 때의 횟수를 비교하여 가장 작은 값을 갱신한다.

from itertools import permutations

N = int(input())
scv = list(map(int, input().split())) + [0, 0]
s, c, v = scv[0], scv[1], scv[2]
dp = {(0, 0, 0) : 0}

# 0,0,0 ~ s,c,v값까지 반복
for i in range(s+1) :
    for j in range(c+1) :
        for k in range(v+1) :
            # 9,3,1의 순열을 받아 s,c,v가 해당 데미지를 받을 때의 횟수를 비교하여 가장 작은 값을 갱신한다.
            for di, dj, dk in permutations([9, 3, 1], 3) :
                dp[(i, j, k)] = min(dp.get((i, j, k), float('inf')),
                                    dp[(max(0, i-di), max(0, j-dj), max(0, k-dk))]+1)

print(dp[(s,c,v)])