(백준) 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

예제 입력

4 7
6 13
4 8
3 6
5 12

정답 : 14

Solution

import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
dp = [0] * (K + 1)  ## 각 무게에 따른 최대 value 값 저장하는 배열
items = [list(map(int, input().split())) for _ in range(N)]
visit = [0] * (K + 1)  ## 사용할 수 있는 무게를 체크 하기 위한 배열 똑같은 무게가 여러번 쓰이는 것을 방지 하기 위함
visit[0] = 1
items.sort()

for weight, value in items:
    for idx in range(K, -1, -1):
        if weight + idx > K or visit[idx] == 0:
            continue
        visit[weight + idx] = 1
        if value + dp[idx] > dp[weight + idx]:
            dp[weight + idx] = value + dp[idx]

print(max(dp))

1. 배낭에 넣을 수 있는 제품을 무게가 작은 순대로 정렬한다.
2. 한 제품을 넣을 때는 dp리스트에서 무게가 높은 순서로 체크해서 넣는다.
   • 작은 무게 부터 더 해버리면 같은 무게가 여러번 들어가는 현상이 생길 수 있다.
3. 작은 무게 부터 배낭에 넣으면서 dp리스트에 같은 무게 일때 높은 value를 저장한다.
4. 그리고 dp리스트에서 가장 큰 값을 프린트 하면 된다!!