12920 평범한 배낭2 파이썬 백준

문제)

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

12920번: 평범한 배낭 2

 

설명)

평범한 배낭1 문제와 다른 점은 물건 개수가 하나였다면 여기는 여러개가 있다.

그래서 최악의 경우 10000(m) * 100(n) * 10000(k)의 연산을 하게 되고 분명 시간초과가 된다.

그래서 이걸 어찌해야하나 고민했지만 모르겠어서 구글링을 해보았다.

 

k를 log2로 줄이는 방법이 존재했다. 앞으로 log로 줄일 수 있는지에 대해 생각해봐야겠다..

모든 자연수는 2의 거듭제곱으로 표현할 수 있다. 이진수 생각하면 이해가 된다.

그래서 만약 물건이 30개가 있다면 1, 2, 4, 8, 15 개로 표현할 수 있다.

objects 라는 리스트에 개수*무게, 개수*만족도를 추가한다.

이렇게 되면 온전히 k개를 반복문에 돌려야 했던 것을 logk개로 반복횟수를 줄일 수 있게 된다.

 

dp는 인덱스는 무게, 값은 만족도로 생각하고

기존 무게와 물건을 넣기 전 무게에서 물건을 넣었을 때의 최대값을 비교하며

dp를 갱신하면 된다.

 

중요한 아이디어는 모든 자연수를 2의 거듭제곱으로 표현할 수 있으니 log로 반복횟수를 줄일 수 있다는 것이다.

 

소스코드 ) 

n, m = map(int, input().split()) # 집 안 물건 종류개수, 가방 최대 무게
objects =[]
# 배낭1 문제는 물건이 하나였으면 여기는 여러개

dp = [0] * (m+1) # index : 무게, 값 : 만족도

# 개수를 dp에 하나씩 넣게 되면 최악의 경우 : 10000(m) * 100(n) * 10000(k) -> 시간초과
# k가 log로 줄어들게 되네

for _ in range(n):
    v, c, k = map(int, input().split())
    # 물건 무게, 만족도, 물건의 개수
    logk = 1
    while k > 0:
        logk = min(logk, k)
        objects.append((v*logk, c*logk))
        k -= logk
        logk *= 2

#print(objects)
for v, c in objects:
    for i in range(m, v-1, -1):
        dp[i] = max(dp[i], dp[i-v] + c)

print(dp[m])