백준 12865번 파이썬 문제풀이(평범한 배낭) - DP(탑다운)

---

이런 문제는 그냥 탑다운으로 풀어버리는 습관을 가져버렸다. C++이면 무조건 통과인데 N이 조금더 커지면 파이썬은 재귀제한을 풀어도 재귀 스택 용량 초과로 불가능하다... 하지만 이러한 재귀 식을 한번 이해해버리면 아주 풀기가 쉽기 때문에 탑다운 방식을 애용하자. (평균적인 재귀와는 달리 끝까지 재귀를 타고 들어가서 한개씩 쌓아서 나오는 구조이다.)

def dfs(depth, weight):
    global ans

    if weight > K:
        return -100000000

    if depth == N:
        return 0

    if dp[depth][weight] != -1:
        return dp[depth][weight]

    dp[depth][weight] = max(dfs(depth + 1, weight + bag[depth][0]) + bag[depth][1], dfs(depth + 1, weight))

    return dp[depth][weight]


N, K = map(int, input().split())

bag = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[-1] * (K + 1) for _ in range(N + 1)]
ans = 0

print(dfs(0, 0))