[코딩 테스트 연습(파이썬/Python)] 백준 12865번 _ 평범한 배낭

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

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)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

[출력]

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

 

[아이디어]

1) DP 문제임을 파악했다면, subproblem을 잘 정의해야한다.

2) subproblem을 정의할 때, 이전에 경우로부터 꼭 물건을 추가하는 것이 아니라 추가하거나 추가하지 않는 둘 중 하나를 택해야 함에 유의해야한다.

3) 이 문제에서 DP가 가져야하는 변수는 'i: 물건의 갯수, j: 배낭의 무게 제한'으로 2개이므로, 2차원 배열이 필요하다.

4) 각 물건들을 가지고 무게제한 0~K 사이의 모든 배낭들을 채우거나 채우지 않으면서, 각 순간의 최대 가치(V)를 업데이트 해나간다.

5) knapsack problem 중 각 물건이 1개씩 존재하고 쪼갤 수 없는 0-1 problem에 해당한다.

a,b = map(int, input().split())
# dp 생성, dp[i][j]는 j의 무게 제한에서 i개의 물건을 포함하는 경우 가치의 최댓값을 의미
dp = [[0 for _ in range(b+1)] for _ in range(a+1)]
# 0개의 물건을 가지는 경우 모두 0이므로 1부터
for i in range(1,a+1):
    c,d = map(int, input().split())
    # 0의 무게 제한을 가지는 경우 모두 0이므로 1부터
    for j in range(1,b+1):
        # j-c<0인 경우는 존재하지 않으므로 제외
        if j-c>=0:
            # (i-1)개의 물건을 가졌다가 'c' 무게의 물건을 추가하지 않거나 추가하는 둘 중 하나다.
            # 후자의 경우 이전 row에서 (j-c)의 무게를 가졌어야 한다. 즉, (j-c)는 음수이면 안된다.
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-c]+d)
        else:
            dp[i][j] = dp[i-1][j]
print(dp[a][b])

벽을 심하게 느끼고 강의까지 찾아보았다,,^ 코드 강의가 아니긴 했지만 보고 나서도 헤매다가 해결했다. DP의 대표적 문제인 knapsack problem의 일종이라고 한다. 가방에 아무것도 없는 경우(i=0)와 무게 제한이 0인 경우(j=0)를 잘 설정해두고 활용하는 것 역시 중요해보인다.