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

---

소스코드

n = int(input())
scv = list(map(int, input().split()))
scv.extend([0, 0])

dp = [[[0]*61 for _ in range(61)] for _ in range(61)]
dp[scv[0]][scv[1]][scv[2]] = 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:
                        dp[i_][j_][k_] = dp[i][j][k]+1

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

---

알고리즘

예전에 푼 문제가 블로그에서 가장 높은 조회수를 달성했는데 그만큼의 퀄리티가 나오지 않아서 풀이를 다시 작성해봅니다.

 

1. scv라는 리스트에 현재 체력을 입력 받습니다. scv = [12, 10, 4]
2. scv의 체력이 60까지이므로 60의 크기에 n차원 dp 배열을 생성합니다. [[[0,0 ,,, (60개)]], ,,, (60개)]] ,,,, (60개)]
3. dp에는 체력에 따른 맞은 최소 횟수가 들어갑니다.
4. dp[scv[0]][scv[1]][scv[2]] = 1 -> dp[12][10][4] = 1 로 초기 값을 세팅해줍니다. (나중에 빼줌)
5. comb는 scv들이 맞을수 있는 공격의 경우의 수를 나열해 놓았습니다.
6. dp를 60, 60, 60 부터 순회합니다. 그러면 [12][10][4] (초기값) 그 위에는 pass 되겠죵
7. dp[12][10][4] = 1 로 초기화된 값을 만나면 comb에 있는 값을 순회합니다.
   1. 12, 10, 4 였는데 9, 3, 1의 데미지를 받았다
   2. 12, 10, 4 였는데 9, 1, 3의 데미지를 받았다 등
8. dp[3][7][3] 이 0 이거나 (이 체력에 처음 도달한 경우) or 그 전보다 적게 맞았으면 ([12][10][4] = 1 인데 [3][7][3] = 3이상 이면) 그 전에 맞은 횟수 + 1이 최소이므로 갱신해줍니다.
9. 그 후 모든 scv 체력이 0,0,0 인 값에서 맨 처음 초기 세팅값 1을 빼줍니다.

스타크래프트는 여전히 하고싶네요 :)

---

이게 맞나 싶을정도로 다 돌려서 해봤는데 맞긴 맞았다.

scv는 1 ~ 3마리이므로 3차원 배열을 선언해주고 1마리나 2마리일 경우는 0으로 채워주면 된다.

for문 3개를 돌아가면서 공격(9,3,1) 3개 조합

comb = [(9, 3, 1), (9, 1, 3), (3, 9, 1), (3, 1, 9), (1, 9, 3), (1, 3, 9)]을 하나씩 빼주면서 0이하일땐 0이되게 계산해주면 된다.

그리고 dp에 저장하면된다.

스타크래프트하고 싶다.