Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-12865-평범한 배낭

O(NK) 로 풀 수 있다. 다만, dictionary를 이용하면 더 빠른 풀이가 가능하다.

Nåive DP -> 2612 ms 소요

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
Ws,Vs = [],[]
for _ in range(N):
    w,v = map(int, input().split())
    Ws.append(w)
    Vs.append(v)

# O(NK) 가능
dp = [-1 for _ in range(K+1)]
dp[0] = 0
for n in range(N):
    W,V = Ws[n], Vs[n]
    for k in range(K,-1,-1):
        if k-W >= 0 and dp[k-W] != -1:
            dp[k] = max(dp[k], dp[k-W]+V)

print(max(dp))

Dictionary DP -> 1712 ms 소요

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
Ws,Vs = [],[]
for _ in range(N):
    w,v = map(int, input().split())
    Ws.append(w)
    Vs.append(v)

# O(NK) 가능
dp = {0:0}
for n in range(N):
    W,V = Ws[n], Vs[n]
    cache = {}
    for key in dp.keys():
        if key+W < K+1:
            cache[key+W] = max(dp[key] + V, dp.get(key+W,0))
    dp.update(cache)

print(max(dp.values()))
Comments