https://www.acmicpc.net/problem/12869
1. scv는 1~3마리 이므로 3마리보다 작을 때 체력이 0인 scv를 넣어준다.
2. 최대 체력은 60이므로 60인 3차원배열을 만들어준다.
3. 체력이 음수로 내려가나 0이나 같으므로 음수로 내려가면 0으로 설정해주고 9, 3, 1을 순서를 바꾸어 dfs
를 돌려준다.
n = int(input())
scv = list(map(int, input().split()))
dp = [[[0 for _ in range(61)] for _ in range(61)] for _ in range(61)]
while len(scv) < 3:
scv.append(0)
def dfs(x, y, z):
if x == 0 and y == 0 and z == 0:
return 0
if dp[x][y][z]:
return dp[x][y][z]
dp[x][y][z] = 1 + min(dfs(max(x-9, 0), max(y-3, 0), max(z-1, 0)), dfs(max(x-9, 0), max(y-1, 0), max(z-3, 0)), dfs(max(x-3, 0), max(y-9, 0), max(z-1, 0)),
dfs(max(x-3, 0), max(y-1, 0), max(z-9, 0)), dfs(max(x-1, 0), max(y-3, 0), max(z-9, 0)), dfs(max(x-1, 0), max(y-9, 0), max(z-3, 0)))
return dp[x][y][z]
print(dfs(scv[0], scv[1], scv[2]))
'알고리즘 > BOJ' 카테고리의 다른 글
[Python] 백준 2591번: 숫자카드 (0) | 2021.11.22 |
---|---|
[Python] 백준 2643번: 색종이 올려 놓기 (0) | 2021.11.21 |
[Python] 백준 1563번: 개근상 (0) | 2021.11.19 |
[Python] 백준 1194번: 달이 차오른다, 가자. (0) | 2021.11.19 |
[Python] 백준 2250번: 트리의 높이와 너비 (0) | 2021.11.18 |
댓글