백준 #12865 평범한 배낭

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


"""
dp[i]: i 크기의 무게를 가졌을 때 최대 가치
"""
n, k = map(int, input().split())
dp = [0] * (k + 1)
for _ in range(n):
    w, v = map(int, input().split())
    for i in range(k, w - 1, -1):
        if dp[i] < dp[i - w] + v:
            dp[i] = dp[i - w] + v

print(dp[k])

:start: 풀이

dp문제를 접했으면 한번쯤은 풀어 봤을 냅색문제(배낭문제)이다

dp[i]를 i 크기의 무게를 가졌을 때 최대 가치로 설정 후,

최대 무게부터 현재 무게를 담을 수 있는 곳 까지 확인하면서 최대 가치를 갱신해준다