책너두 - 알고리즘 챌린지[18/20]

오늘의 문제 : 평범한 배낭 2

오늘의 문제는 dp와 비트마스킹을 활용해야 문제를 풀 수 있었다.

가뜩이나 dp문제는 점화식을 찾기 어려워 오래 걸리는 경우가 많은데, 비트마스킹을 활용하지 않으면 메모리 초과가 발생하는 문제라 어려웠다.

문제 풀이 방식은 dp를 1차원으로 만들고, 물건을 담는 경우를 비트마스킹으로 구분하는 것이다.

먼저, 전체 코드를 살펴보면 다음과 같다.

import sys
n, m = map(int, sys.stdin.readline().split())
items = []
dp = [0 for _ in range(m+1)]
for _ in range(n) :
    v, c, k = map(int, sys.stdin.readline().split())
    
    tmp = 1
    while k > 0 :
        _min = min(tmp, k)
        items.append((v * _min, c * _min))
        k -= tmp
        tmp *= 2
    
for weight, customer in items :
    for i in range(m, weight-1, -1) :
        dp[i] = max(dp[i], dp[i-weight] + customer)

print(dp[m])

while 부분을 살펴보면, k개가 있는 물건을 (k보다 적은 2의 배수로) 1개, 2개, 4개, ... 단위로 배열에 저장한다. 해당 방식을 활용하면, 배열을 k개 담는게 아닌 2의 배수로 저장할 수 있기 때문에 메모리 부분에서 효율적이다.

이후 for 문을 순회하며, 기존 dp테이블 만들었던 것 처럼 만들면 된다!