문제

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

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

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

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

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

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

# 12869
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

n = int(input())
f, s, t = 0, 0, 0
if n == 1:
    f = int(input())
elif n == 2:
    f, s = map(int, input().split())
else:
    f, s, t = map(int, input().split())
    
scv = [[[-1] * (t+1) for _ in range(s+1)] for _ in range(f+1)]

dx, dy, dz = [-9, -9, -3, -3, -1, -1], [-3, -1, -9, -1, -9, -3], [-1, -3, -1, -9, -3, -9]

def bfs():
    global f, s, t, scv
    queue = deque()
    queue.append((f, s, t))
    scv[f][s][t] = 0
    
    while queue:
        x, y, z = queue.popleft()
        
        if x == y == z == 0:
            continue
            
        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
            if nx < 0:
                nx = 0
            if ny < 0:
                ny = 0
            if nz < 0:
                nz = 0
                
            if scv[nx][ny][nz] == -1 or scv[x][y][z] + 1 < scv[nx][ny][nz]:
                scv[nx][ny][nz] = scv[x][y][z] + 1
                queue.append((nx, ny, nz))
                
bfs()
print(scv[0][0][0])

백준 12869 뮤탈리스크