백준 12920 : 평범한 배낭2 (Python)

본문 링크

import sys
input=sys.stdin.readline

"""
12920번 : 평범한 배낭 2

배낭문제와 다른점은 물건의 개수가 1개가 아니라는점이다.
중요한 것은 물건의 개수를 어떻게 처리할 것인가? 이다.

이는 분할정복을 이용하여서 물건의 개수가 15개라면 [1,2,4,8] 로 나누어준다.
이러면 임의의 리스트 값을 어떻게든 선택하면 1~15의 값을 모두 만들 수 있다.

즉 물건의 종류 1개에 개수가 15개인것을 물건의 종류 4개로 만들고 개수를 분할해주는것이다.

만약 물건의 5개라면 [1,2,(5-1-2)=2] 로 설정을 해준다.

2의 제곱수들의 리스트는 모든 수들을 나타낼수 있다.


"""
N,M=map(int,input().split()) #N은 물건의 개수 M은 가방의 크기

check=0  ; L=[]

for i in range(N):
    V,C,K=map(int,input().split()) # V는 무게 C는 가치 K는 물건의 개수
    check=0 ; sum=0
    while True:
        sum+=2**check
        if sum<=K:
            L.append([V*(2**check) , C*(2**check)])
            check+=1
        else:
            if K -(sum-2**check)!=0:
                L.append([V*(K-(sum-2**check)) ,C*(K-(sum-2**check))])
            break


dp=[ [0]*(M+1) for _ in range(len(L)+1)]


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

print(dp[len(L)][M])

📌 어떻게 접근할 것인가?

기본적인 배낭문제입니다.

단 한가지 다른점은 물건의 개수가 주어진다는 것입니다.

따라서 물건의 개수를 어떻게 처리할것인가? 에 대해 중심적으로 생각해야합니다.

물건의 종류 , 물건의 무게 , 물건의 개수를 모두 고려하게 되면 $O(NVK)$ 로 아주 많은 시간을 소비하게 됩니다.

시간을 줄이기 위하여 물건의 개수를 최적화 하는 방법에 대해 알아보겠습니다.

📌 물건의 개수를 어떻게 최적화 할것인가?

물건이 15개가 있으면 꼭 15번의 연산을 해야할까요?

여기 아주 중요한 이론이 하나가 있습니다.

2의 거듭제곱의 리스트는 모든 수의 합을 임의의 수들의 합으로 나타낼수 있다

$[1,2,4,8]$ 이라는 리스트가 있다고 가정합니다. 이 리스트는 $2^0 , 2^1 , 2^2 , 2^3$ 으로 구성되어있습니다.
이때 이 리스트의 값들을 적절히 선택하여서 더하면 1부터 15까지의 모든 수들을 나타낼 수 있습니다.

• 1=1
  2=2
  3=1+2
  4=4
  5=1+4
  6=2+4
  7=1=2+4
  8=8
  9=1+8
  10=2+8
  11=1+2+8
  12=4+8
  13=1+4+8
  14=2+4+8
  15=1+2+4+8

즉 물건의 종류 1개에 개수가 15개인것을 물건의 종류 4개로 만들고 개수를 분할해줍니다.
이러면 물건의 개수가 1부터 15일때의 경우를 모두 계산할 필요없이
단순히 물건의 종류가 4개라고 생각할수있습니다.

따라서 한번의 반복문과 while 문을 사용하여서 물건을 여러종류로 분할 해주고
이후 일반적인 배낭문제에 사용되는

• $dp[i][j]=max(dp[i-1][j-weight]+value , dp[i-1][j] )$

점화식을 사용해주면 답을 구할수 있습니다.

✅ 문제를 풀면서 느낀점

물건의 개수가 여러개 있는것을 분할해서 여러 종류로 만들어버린다는 아이디어를 처음듣고 조금 충격을 먹었습니다.
또한 "2의 거듭제곱으로 이루어진 리스트는 모든 수의 합을 나타낼수있다" 라는 것은 예전에 한번 구해본적이 있는데 이렇게 써먹을줄은 몰랐습니다.

배낭문제를 공부하는 사람이라면 이 문제를 꼭 추천해보고싶을정도로 좋은 문제인거같습니다.

최근에 백준에서 Python 새 버전이 도입되면서 속도가 향상되어 그냥 모든 경우의 수를 탐색하는 코드도 통과가 되긴하는데 개인적으로 이런 최적화 방법을 직접 구현해보면 좋겠습니다.