백준 12865번 - 평범한 배낭

평범한 배낭 문제 바로 가기

풀이 날짜: 2026-01-11

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
bag = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1,n+1):
    w,v = bag[i-1]
    for j in range(1,k+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])
  

문제 핵심 요약:

이 문제는 물건이 여러 개 주어지고, 각 물건마다 무게와 가치가 있다.
배낭에는 최대 무게 K까지 물건을 담을 수 있고, 각 물건은 한 번만 넣을 수 있다.

내가 선택한 풀이 방식

앞에서 어떤 물건을 선택했는지가 뒤에서 선택 가능한 물건 조합에 영향을 주기 때문에, 모든 경우를 효율적으로 누적 관리할 방법이 필요했다.
따라서 앞에서 i개의 물건을 고려했을 때의 최적 상태를 저장해야 하기 때문에 DP로 풀었다.

반복문

• i번째 물건을 넣을지 말지 결정하면서
• 배낭 용량이 1부터 k까지일 때의 최적 값을 채워나간다.

즉, 행은 물건의 개수를, 열은 배냥 용량을 의미하는 표를 채우는 과정이다.

헷갈렸던 핵심 포인트

• dp 배열의 의미를 명확히 정의하지 않으면 인덱스가 헷갈린다
• i와 bag[i-1]의 대응 관계를 놓치기 쉽다
• dp는 과정이 아니라 상태를 저장한다는 점을 계속 상기해야 한다