12920. 평범한 배낭 2

솔루션을 보고 해결한 문제이며, 공부용으로 기록함을 밝힙니다.

12920번: 평범한 배낭 2 (acmicpc.net)

12920번: 평범한 배낭 2

---

12865. 평범한 배낭 문제에서는 모든 물건이 1개였는데, 이 문제에서는 물건이 여러 개일 수 있다. 여러 개의 물건을 처리하는 가장 쉬운 방법은 서로 다른 물건으로 취급하여 푸는 것이다. 그러나 이렇게 풀면 물건이 최대 1만 개이고, 배낭의 무게가 최대 1만이므로 총 1억 번의 계산을 해야 한다. 이러면 시간 초과가 난다.

 

따라서 물건을 하나씩 따로 취급하면 안 된다. 가짓수를 덜 나누면서도 물건을 고르는 모든 경우의 수를 만들 수 있어야 한다.

 

이 문제에서 사용하는 해법은, 물건 수를 2의 거듭제곱 꼴로 나누는 것이다. 예를 들어 물건 7개를 1, 2, 4개로 쪼개면, 0개부터 7개까지의 모든 경우의 수를 만들 수 있다.

 

정확히는 아래 코드처럼 나누면 된다. 이렇게 하면 2의 거듭제곱 합으로 나타낼 수 없는 나머지까지 포함할 수 있다. 예를 들어 $10,000$은 다음과 같이 나뉜다.

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 1809 

int square = 1;
while (k > 0)
{
    int count = std::min(k, square);
    // 물건 push
    k -= count;
    square <<= 1;
}

물건이 최대 14개로 나눠지므로 dp 배열의 크기를 1400 × 10001로 놓고 계산하면 된다. 배열을 채우는 방법은 일반적인 냅색 dp처럼 하면 된다.

---

발상이 참 신기한 문제. 두고두고 써먹을 수 있을 것 같다.