[백준/Python] 12865번 - 평범한 배낭

 

문제

https://www.acmicpc.net/problem/12865

 

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

 

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

 

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다.

 

아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

 

 

입력

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다. 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

 

출력

 

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

 

 

풀이

 

DP를 이용해 풀었다. 처음에는 가방의 무게와 Value를 전부 받아 리스트로 저장한 뒤 i번째 가방이 들어가는지 안들어가는지 비교하며 리스트에 max값을 저장하며 풀었다.

 

일반적인 점화식은 다음과 같다. i번째 원소까지 비교했을 때 최대값을 DP[i][W]라고 할 때,DP[i][W]=max(DP[i-1][W], DP[i-1][W-wi]+vi)로 표현할 수 있다.

 

i번째 원소를 포함하지 않고 가방의 무게 W를 채우는 경우와 i번째 원소를 포함해 가방의 무게 W를 채우는 경우의 최대값을 비교하면 된다.

 

처음에는 무게 W와 i번째 요소로 이루어진 2차원 리스트를 만들어 DP로 풀었는데 생각해보니, 모든 무게 마다 비교할 필요 없이 배낭에 물건을 저장했을 때 가능한 무게들만 비교하는게 더 빠르겠다는 생각이 들었다.

 

그래서 이를 dictionary로 바꿨고 dic 에 {weight1:value1, weight2:value2...}와 같이 저장했다.

 

그리고 i번째 원소를 포함했을때 무게와 안했을때의 무게들이 최대로 저장할 수 있는 무게 W를 넘는지를 검사하고 만약 안넘는다면 이전에 dictionary에 해당 무게가 있는지 비교해서 최대값을 저장하도록 코드를 짰다.

 

 

 

Code

 

 

import sys
input=sys.stdin.readline
def bag():
    DP={0:0} // 무게를 저장할 Dic
    for i in range(N):
        u={} // 새로 바뀐 무게 별 최대 value값을 저장할 dic
        weight,value=map(int,input().split())
        for w,v in DP.items():
            a=w+weight // 무게가 가능한 최대 무게를 넘는지 비교
            if a<=M:  // 최대 무게를 안 넘는다면
                c=DP.get(a)
                if c: // 만약 dic에 무게 a가 저장되어 있다면 Value값을 비교해 최댓값을 저장
                    u[a]=max(c,v+value)
                else: // 없다면 dic에 무게 a 추가
                    u[a]=v+value
        DP.update(u)
    print(max(DP.values()))

N,M=map(int,input().split())
bag()

 

---

 

DP문제들은 점화식을 잘 세워야 하는 문제들이 많은 것 같다

 

 

 

12865번: 평범한 배낭