[백준] 12869 뮤탈리스크 - 파이썬

문제

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

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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

 

---

풀이

 

scv를 공격하는 순서, 공격하는 횟수, 각 scv의 체력, scv의 번호

 

이 네개의 값들 중 dp 배열을 구성할 컬럼값 + 그 안에 저장할 값을 정해야겠다고 생각했다.

근데 이렇게 저렇게 조합해봐도 잘 안 풀렸다..

 

다른 분의 글을 조금 훔쳐보고 깨달았다 ..

3차원 배열을 구성하는데 모든 컬럼값이 체력이었다.

배열 내부에 들어갈 값은 예상했던대로 횟수였다.

 

대부분 dp문제에서 정답에 해당하는 값이 배열 내부에 들어가는 것 같다.

 

자세한 풀이는 다음과 같다.

 

dp[i][j][k]에서 i, j, k는 각 scv의 체력을 나타낸다.

dp 배열 내부에 들어가는 값은 해당 체력을 만드는 데 필요한 최소 공격횟수이다.

 

처음 scv의 체력대로 배열을 초기화하고

배열을 순회하며 모든 경우의 수의 공격을 한다.

 

만약 아직 i, j, k 의 체력을 만든 적이 없다면 해당 체력을 만들기 위해 한 공격의 횟수를 저장해준다.

이전 공격 횟수의 +1을 하면 된다.

 

다만 0 미만이 되는 경우는 모두 0으로 변경해주기 때문에

더 적은 횟수의 공격으로도 같은 위치에 도달할 수 있다.

 

예를 들어 scv의 체력이 각 10, 0, 0일 때

-1, -9, -1 을 하면 7, 0, 0 에 도착하기 위해 3번의 공격을 해야하는데

-3, -9, -1 을 하면 7, 0, 0을 1회만에 도착할 수 있다.

 

때문에 더 적은 횟수로 도착하는 경우 dp값을 변경해준다.

 

모든 순회를 마치고 0,0,0에 저장된 값을 출력해준다.

 

 

n = int(input())
scv = list(map(int, input().split()))
scv.extend([0, 0]) #3개 미만이 들어왔을 때 개수 맞춰주기

dp = [[[0]*61 for _ in range(61)] for _ in range(61)] #각 위치에 도달하는 횟수 저장
dp[scv[0]][scv[1]][scv[2]] = 1 #초기화, 0인데 1로 초기화했으므로 나중에 1 빼주기

comb = [(9, 3, 1), (9, 1, 3), (3, 9, 1), (3, 1, 9), (1, 9, 3), (1, 3, 9)]
for i in range(60, -1, -1):
    for j in range(60, -1, -1):
        for k in range(60, -1, -1):
            if dp[i][j][k] > 0:
                for c in comb:
                    i_ = i-c[0] if i-c[0] >= 0 else 0
                    j_ = j-c[1] if j-c[1] >= 0 else 0
                    k_ = k-c[2] if k-c[2] >= 0 else 0
                    if dp[i_][j_][k_] == 0 or dp[i_][j_][k_] > dp[i][j][k]+1:
                    # 처음 도착한 경우 or 더 적은 횟수로 도착하는 경우에만 업데이트
                        dp[i_][j_][k_] = dp[i][j][k]+1

print(dp[0][0][0]-1)

출력예시가 많아서 예외를 잡는데 편했다.