백준
[백준/dp] 12869번 : 뮤탈리스크
ydin
2024. 2. 15. 12:08
- 문제 : https://www.acmicpc.net/problem/12869
정답 풀이
주어진 각 scv의 체력을 각각 감소 시키는데 0, 0, 0을 만드는데 최소한의 횟수를 구하는 문제다.
어떻게 풀어야할지 잘 몰랐는데 블로그를 참고하니 3차 행렬을 이용하면 된다고 한다.
1. dp[i][j][k]는 각 scv의 체력이 i, j, k일 때의 공격 받은 횟수를 의미한다.
2. 삼중 for문으로 배열을 순회하며 모든 경우의 수([1, 3, 9]의 permutation = 3!)를 고려해 공격한다. 공격하면 인덱스가 줄어든다.
3. 아예 처음인 체력(dp[][][] == 0)이거나 현재 있는 체력 값보다 이전 체력값 + 1이 더 작은 경우에 업데이트 한다.
if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:4. dp[0][0][0]은 모든 체력이 0, 0, 0일 때의 최소 공격 수 이므로, 출력한다. 이때 초기화하느라 1을 추가했으므로 이를 빼주고 출력해줘야 한다.
n = int(input())
scv = list(map(int, input().split())) + [0, 0] # 3개 미만이 들어왔을 때 개수 맞춰주기 위함
# dp[i][j][k] 값은 각 scv 체력이 i, j, k 일 때 공격 받은 횟수를 의미한다
dp = [[[0] * 61 for _ in range(61)] for _ in range(61)]
dp[scv[0]][scv[1]][scv[2]] = 1 # 1로 초기화, 마지막에 1을 빼줘야 한다
case = [[1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]]
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 case:
ni = max(i - c[0], 0)
nj = max(j - c[1], 0)
nk = max(k - c[2], 0)
# 처음 도착한 경우 or 더 적은 횟수로 도착하는 경우에만 업데이트
if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:
dp[ni][nj][nk] = dp[i][j][k] + 1
print(dp[0][0][0] - 1)