12920 - 평범한 배낭 2
📌 문제
이 문제는 아주 평범한 배낭에 관한 두 번째 문제이다.
민호는 BOJ 캠프에 가기 위해 가방을 싸려고 한다. 가방에 어떠한 물건들을 넣냐에 따라 민호의 만족도가 달라진다. 집에 있는 모든 물건들을 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다. 하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다.
민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자.
단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두 개 이상 챙기는 것도 가능하다.
📋 코드
N, M = map(int, input().split())
dp = [0 for _ in range(M+1)]
weight, satisfaction = [], []
for _ in range(N):
V, C, K = map(int, input().split())
idx = 1
while K > 0:
tmp = min(idx, K)
weight.append(V * tmp)
satisfaction.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]] + satisfaction[i])
print(dp[M])💡 한마디
시간 초과 때문에 굉장히 애먹었고, 왜 플래티넘인지 몸소 느낀 문제였다.
- 첫번째 풀이 : K개 물건 전부 입력받아 2차원 DP 테이블을 만들고, 배낭정리 풀이 -> 시간 초과
- 두번째 풀이 : 2차원 테이블을 1차원으로 수정하여 풀이 -> 시간 초과
한 시간 반 정도 붙잡고 있다가 도저히 안풀려 검색해보니 비트마스크 개념을 도입하는 사람들이 많았다.
모든 자연수는 2의 거듭제곱의 합으로 나타낼 수 있기 때문에 물건을 1개씩 추가해주는 것이 아니라 2의 거듭제곱씩 추가해도 모든 수를 고려할 수 있다.
만약 같은 물건 15개가 있다고 생각해보자. 15는 1 + 2 + 4 + 8 이기 때문에 물건을 1개, 2개, 4개, 8개 추가한 경우를 모두 DP 테이블에 갱신시켜주면 됐다.
