import sys
# 물품의 수, 최대 무게
n, capacity = map(int, sys.stdin.readline().rstrip().split())
cargo = []
for _ in range(n):
w, v = map(int, sys.stdin.readline().rstrip().split())
# (가치, 무게) = (v, w)
cargo.append([v, w])
pack = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for c in range(1, capacity + 1):
# i번째 물건의 무게가 배낭의 용량보다 작다면 (=일단 넣을 수 있기라도 한다면)
if cargo[i-1][1] <= c:
a = cargo[i-1][0] + pack[i-1][c - cargo[i-1][1]]
b = pack[i-1][c]
pack[i][c] = max(a, b)
else:
pack[i][c] = pack[i-1][c]
print(pack[-1][-1])
처음부터 완전한 크기의 pack
배열을 선언하지 않고, for문마다 한 행씩 생성했을 경우 시간초과가 발생했다. 상향식 풀이인 타뷸레이션 방식을 사용했다.