[Gold IV] 뮤탈리스크 - 12869 (DP)

[Gold IV] 뮤탈리스크 - 12869

문제 링크

성능 요약

메모리: 33300 KB, 시간: 64 ms

분류

너비 우선 탐색(bfs), 다이나믹 프로그래밍(dp), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이방법

핵심 조건과 출력해야 할 값을 먼저 살펴본다.

스타크래프트를 한 번쯤 해본 사람이라면 문제 이해는 굉장히 쉽게 할 수 있다. 뮤탈의 공격 패턴을 그대로 생각하면 되기 때문이다.

결국에 뮤탈은 공격 순서에 따라 scv의 체력을 9, 3, 1을 깍을 수 있기 때문에 모든 경우의 수를 따져보면 순열을 생각할 수 있다. 또한, scv를 모두 죽일 수 있는 공격 횟수의 최솟값을 구하는 문제이므로, dp 혹은 bfs도 생각해볼 수 있다.

나의 경우, dp가 약하기 때문에 풀이를 조금씩 찾아보며 내가 이해를 쉽게 할 수 있는 방식으로 문제를 풀었다.

 

1. 최대 세 개의 scv를 때릴 수 있고, 총 scv 개수가 3 최대 3개만 주어지기 때문에  dp를 수행할 리스트를 3차원 배열로 만들어준다. 각 차원의 배열은 각각 scv의 체력을 뜻한다. 체력의 default 값은 문제에 주어진 최대 체력 60보다 1 넘는 61로 넣어준다.

 

2. 순열을 이용하여 뮤탈이 공격할 수 있는 모든 경우의 수를 판단할 per함수를 만든다.

 

3. 모든 경우의 수로 계속 공격하다보면 모든 scv 체력이 0이 되는경우가 생기는데, 그 때의 최소 공격 횟수를 계속 초기화하며 최솟값을 찾아준다. ( 기저 부분 )

 

4. dp 배열의 인덱스를 벗어나지 않기 위해 scv 체력이 0 이하로 내려가면, 그 scv의 체력은 무조건 0으로 초기화 해준다.

 

5. scv들의 체력들에 저장된 값. 즉, 공격 횟수가 현재 함수가 실행하고 있는 횟수(cnt)보다 작거나 같을 경우는 기존에 default값으로 저장한 61보다 작은 수 이므로, 이미 방문한(공격했던 경우의 수) 곳이며 더 최소 공격 횟수로 때릴 수 있었던 경우이므로 더 이상 함수를 돌지 않고, 리턴해준다.

 

6. 2~5번을 재귀 호출하여 계속 실행하며 최종 값인 최소 공격 횟수(hp_max)를 출력하면 문제 해결.

from itertools import permutations as pt

def per(x, y, z, cnt):

    global hp_max

    if x <= 0 and y <= 0 and z <= 0: # scv를 모두 처치했을 때
        hp_max = min(hp_max, cnt) # 처치한 최소 공격횟수 초기화
        return

    if x <= 0: x = 0
    if y <= 0: y = 0
    if z <= 0: z = 0

    # 이미 방문했고, 지금보다 최소 공격횟수인 scv 체력들이면 리턴
    if dp[x][y][z] <= cnt:
        return

    dp[x][y][z] = cnt

    # 순열 : 뮤탈이 할 수 있는 모든 공격 방법으로 scv 체력을 깎는다
    for i in pt([9,3,1], 3):
        per(x - i[0], y - i[1], z - i[2], cnt + 1)

N = int(input())
scv = list(map(int,input().split()))
while len(scv) < 3:
    scv += [0]
scv_max_hp = max(scv) # scv 중 최대 체력
hp_max = 61 # scv 체력이 될 수 없는 default 값
dp = [[[hp_max] * (scv_max_hp +1) for _ in range(scv_max_hp+1)] for _ in range(scv_max_hp+1)]
per(scv[0], scv[1], scv[2], 0)

print(hp_max)