[백준 12920번] 평범한 배낭 2 (Python3)

import sys
input = sys.stdin.readline

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

stuff = []
for _ in range(N):
  w,c,k = map(int,input().split())
  l = len(bin(k))-3; k -= (1<<l)-1
  for i in range(l):
    stuff.append((w*(1<<i),c*(1<<i)))
  for i in range(l+1):
    if k&(1<<i):
      stuff.append((w*(1<<i),c*(1<<i)))
      
N = len(stuff)
DP = [[0]*(M+1) for i in range(N+1)]
for n in range(1,N+1):
  w,c = stuff[n-1]
  for m in range(1,M+1):
    DP[n][m] = DP[n-1][m]
    if w<=m:
      DP[n][m] = max(DP[n][m],DP[n-1][m-w]+c)    
print(max(DP[N]))

평범한 배낭 [백준 12865번] 평범한 배낭 (Python3) (tistory.com) 문제의 업그레이드 버전이다.

그냥 단순하게 각 물건의 개수 K에 대해서 냅색 알고리즘을 사용하면 시간복잡도가 O(NMK)가 되어버려 풀 수 없게된다.

따라서 이를 최적화하는 아이디어가 필요하다.

 

어떻게 최적화할 수 있을지 고민하다가 결국 질문게시판에서 힌트를 얻었는데, 바로 이진법을 이용하는 것이었다.

예를들어 K=15일 경우, K개의 물건이 있는 것이 아니라, 물건이 1개, 2개, 4개, 8개가 있다고 생각하는 것이다.

그럼 모든 수 조합을 나타낼 수 있을뿐만 아니라 시간복잡도를 O(NMK)에서 O(NMlogK)로 단축시킬 수 있다.

 

문제는 어떻게 K를 분해할 것인가인데, 15의 경우에는 비트가 1111이기 때문에 상관없지만 8같은 숫자의 경우 비트가 1000인데 이는 어떻게 처리하는지가 관건이었다.

나는 이를 현재 수보다 작은 모든 비트가 1인 수를 구하고, 이를 빼준 뒤 비트연산을 하는 방법을 선택하였다.

 

예를들어 11이라는 숫자가 있으면 비트는 1011이 된다. 11보다 작으면서 모든 비트가 1인 수는 7(111)이다.

따라서 물건을 1개, 2개, 4개를 넣은 뒤, 11-7=4=100, 4개를 또 넣는 것이다.

 

 

참고로 다른 사람들 풀이를 읽으면서 숫자를 더 쉽게 분해할 수 있는 방법이 있다는 것을 알게되었다. 예를들어 11이 있으면 11-11//2=6, 5-5//2=3, 2-2//2=1, 1로 2로 나눠주면서 나눈 값을 뺀 개수를 포함시키는 것이다.

그럼 1+1+3+6 = 11이고, 1,1,3,6을 이용해서 11 이하의 모든 수를 나타낼 수 있게 된다.

 

 

오늘의 교훈) 비트연산을 활용하자