문제

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

민호는 BOJ 캠프에 가기 위해 가방을 싸려고 한다. 가방에 어떠한 물건들을 넣냐에 따라 민호의 만족도가 달라진다. 집에 있는 모든 물건들을 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다. 하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다.

민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자.

단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다.

입력

첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다.

두 번째 줄부터 N개의 줄에 걸쳐 민호의 집에 있는 물건의 정보가 주어진다.

각각의 줄은 V, C, K (1 ≤ V ≤ M, 1 ≤ C, K ≤ 10,000, 1 ≤ V * K ≤ 10,000) 으로 이루어져 있다.

V는 물건의 무게, C는 물건을 가방에 넣었을 때 올라가는 민호의 만족도, K는 물건의 개수이다.

출력

최대 무게를 넘기지 않게 물건을 담았을 때 민호가 느낄 수 있는 최대 만족도를 출력한다.

예제 입력 1

2 3
2 7 1
1 9 3

예제 출력 1

27

예제 입력 2

3 9
8 5 1
1 2 2
9 4 1

예제 출력 2

7

나의 풀이

import sys
input = sys.stdin.readline
N, M = map(int, input().split()) #N: 물건 종류의 수, M: 민호가 들 수 있는 가방의 최대 무게
dp = [0 for _ in range(M + 1)]
weight = []
utility = []
for _ in range(N):
    V, C, K = map(int, input().split()) #V: 물건의 무게, C: 민호가 느끼는 효용, K:물건의 개수

    idx = 1
    while K > 0:
        tmp = min(idx, K)
        weight.append(V * tmp)
        utility.append(C * tmp)

        idx *= 2
        K -= tmp

for i in range(len(weight)):
    for j in range(M, 0, -1):
        if j >= weight[i]:
            dp[j] = max(dp[j], dp[j-weight[i]] + utility[i])

print(dp[M])

풀이 과정

평범한 배낭 문제에서 물건이 중복가능하게 바뀌었을 뿐인데 난이도가 엄청나게 뛰었다.
풀이를 천천히 봐도 이해가 안 되서 이해에 골머리를 앓다가 직접 노트에 예제 1이 정답 코드에서 어떻게 돌아가는지 손으로 일일이 다 써보고 겨우 깨달았다.



이 문제를 풀기 위해 알고 있어야 했던 개념은 2의 제곱 리스트로 모든 수를 만들어 낼 수 있다는 개념이다.
이에 대한 자세한 설명은 여기에서 해답을 얻었다.

예제를 기준으로 보자면 무게 1 가치 9 를 가진 물건이 3개 있으므로, 해당 물건을 무게1 가치9 를 가진 물건 A 와 무게2 가치18을 가진 물건 B(A의 2배) 라고 생각하는 것이다.
그렇다면 weight 리스트에는 = [2,1,2] 가 들어가고, utility 리스트에는 [7, 9, 18]이 들어가는 것이다.
이렇게 되면 해당 물건이 1개 있을 때, 2개 있을 때, 1+2개 있을 때의 모든 경우를 커버할 수 있게 되는 것이다.

풀이가 이해가 안 될때는 직접 손으로 써보는 것도 많은 도움이 된다는 것을 깨달았다.