백준 12869 뮤탈리스크 python

문제 바로가기

문제

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

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

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

첫 번째로 공격받는 SCV는 체력 9를 잃는다.
두 번째로 공격받는 SCV는 체력 3을 잃는다.
세 번째로 공격받는 SCV는 체력 1을 잃는다.
SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

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

입력

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

출력

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

풀이

n = int(input())
scv = list(map(int, input().split()))
# 정보가 주어지는 scv의 수와 상태를 입력받고
while len(scv) != 3:
    scv.append(0)
# 3마리보다 적다면 3마리 1쌍을 맞추어줍니다.
dp = [[[61]*61 for _ in range(61)] for _ in range(61)]
hits = 7 * 7 * 7
# 최대 체력이 60이므로 61 * 61 * 61의 방문표시를 해 줄 dp를 만들어줍니다. 
# 최소 데미지가 1이므로 최대 61번 방문이 가는하다 가정하고 각 인덱스 값은 61로 해줍니다.
# 최대 타격 회수로 7 * 7 * 7을 입력해주었습니다. 
# (각 60을 9의 데미지로 타격하여 0으로 만드는데 필요한 타격 횟수)
def mutal(x, y, z):
    global hits
    x, y, z
    if x <= 0 and y <= 0 and z <= 0:
        hits = min(hits, dp[x][y][z])
        return
        # 함수를 실행시킬 인자값이 0, 0, 0이라면 타격 횟수를 지금 저장된 값과 비교하고
        # 작은 값으로 갱신해주고 값 리턴시켜줍니다. 
    for i in ((9, 3, 1), (9, 1, 3), (3, 1, 9), (3, 9, 1), (1, 9, 3), (1, 3, 9)):
        nx = x - i[0]
        ny = y - i[1]
        nz = z - i[2]
        # 타격 가능한 조합으로 각 유닛들을 공격한다고 가정하고
        if nx < 0:
            nx = 0
        if ny < 0:
            ny = 0
        if nz < 0:
            nz = 0
        # 체력이 0이하로 내려간다면 0으로 바꾸어줍니다.
        if dp[nx][ny][nz] > dp[x][y][z] + 1:
            dp[nx][ny][nz] = dp[x][y][z] + 1
            mutal(nx, ny, nz)
            # dp[nx][ny][nz]에 저장된 값이 더 적은 횟수의 타격으로 만들수 있다면
            # 값을 갱신해주고 타격을 다시 돌려줍니다.

dp[scv[0]][scv[1]][scv[2]] = 0
# 처음 주어진 체력 상태에서 타격 횟수를 0으로 바꾸어 줍니다.
mutal(scv[0], scv[1], scv[2])
# 함수를 작동시켜 가장 작은 타격 횟수를 찾아줍니다.
print(hits)
# 최소 타격 횟수를 출력시켜줍니다.