[플래티넘5] 12920번 : 평범한 배낭2

🛠 문제

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

👩🏻‍💻 해결 방법

중복되는 물건 또한 개별의 물건으로 처리하여 2차원 dp 리스트를 통해 해결하려 했지만 시간초과로 인해 할 수 없었다
다른 사람들의 풀이를 참조하였고, 비트마스크 개념을 사용하는 문제임을 알 수 있었다
모든 자연수는 2의 거듭제곱의 합으로 표현이 가능하므로 물건을 2의 거듭제곱씩 추가하는 경우를 고려하여 dp를 계산해주었다

소스 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [0] * (m + 1)
weight = []
satisfied = []

for _ in range(n):
  v, c, k = map(int, input().split())

  idx = 1
  while k > 0:
    tmp = min(idx, k)

    weight.append(v * tmp)
    satisfied.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]] + satisfied[i])

print(dp[m])