[Python] 12865 평범한 배낭

평범한 배낭

분석

• 각 물건은 무게와 가치를 가짐
• 무게와 가치를 고려하여 버틸 수 있는 무게 안에서 준서가 최대한 즐거운 여행을 하기 위해 넣을 수 있는 물건들의 최댓값

입력

• N: 물품의 수, K: 버틸 수 있는 무게

출력

• 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값

---

접근 방식

• dp를 활용하여 최댓값 갱신하는 방법
• 예를 들어 무게가 1인 친구와 2인 친구의 합이 3번 친구보다 크다면 갱신하는 것으로,,,

틀린 풀이

N, K = map(int, input().split())

L = []
dp = [0 for _ in range(K+1)]

for i in range(N):
    a, b = map(int, input().split())
    L.append([a,b])
    dp[a] = b
# 무게 순으로 정렬
L.sort(key=lambda x:x[0])


for j in range(K-1):
    if j + j+1 <= K:
        dp[j+j+1] = max(dp[j+j+1], dp[j]+dp[j+1])

print(max(dp))

• 무게 순으로 리스트를 정렬하여 앞에서부터 진행했음
  당연히 맞을 줄 알았는데 틀려서 여러 반례를 찾아보다가...
  앞에서부터 접근하는 게 아니라 뒤에서부터 접근해야 된다는 사실을 알았다...
  - 이미 갱신한 값을 또 쓸 수 있기 때문 (6을 구할 때 3+3이 될 수 있다)

그래서 고친 풀이

N, K = map(int, input().split())

L = []
dp = [0 for _ in range(K+1)]

for i in range(N):
    a, b = map(int, input().split())
    L.append([a,b])
    #dp[a] = b
# 무게 순으로 정렬
L.sort(key=lambda x:x[0])


for a, b in L:
    for j in range(K, a-1, -1):
        dp[j] = max(dp[j], dp[j-a]+b)

print(max(dp))