[Baekjoon] 12920 – 평범한 배낭2

📖 문제 이해하기

이 문제는 고전적인 배낭(Knapsack) 문제의 변형입니다. 민호는 캠프에 가기 위해 가방을 싸려고 하는데, 각 물건은 무게와 만족도를 가지고 있습니다. 일반적인 배낭 문제와 다른 점은, 같은 물건을 여러 개 넣을 수 있다는 것입니다. 단, 각 물건은 최대 K개까지만 존재합니다.

예를 들어, 무게 3kg, 만족도 4인 물건이 5개 있고, 가방의 최대 무게가 10kg이라면, 우리는 이 물건을 0개, 1개, 2개, 또는 3개까지 넣을 수 있습니다(4개 이상은 무게 초과). 목표는 가방의 무게 제한 M을 넘지 않으면서 만족도의 합을 최대화하는 것입니다.

입력으로는 물건의 종류 수 N(최대 100개)과 가방의 최대 무게 M(최대 10,000)이 주어지며, 각 물건은 무게 V, 만족도 C, 개수 K로 설명됩니다. 제약 조건을 보면 1 ≤ V * K ≤ 10,000이므로, 한 종류의 물건이 차지할 수 있는 총 무게는 제한적입니다.

🧠 순진한 접근과 그 한계

첫 번째 시도: 물건을 모두 펼쳐놓기

배낭 문제를 처음 접하면 가장 직관적인 방법은 각 물건을 개별 아이템으로 취급하는 것입니다. 만약 어떤 물건이 5개 있다면, 이를 5개의 독립적인 물건으로 보고 일반적인 0-1 배낭 문제로 풀면 됩니다.

이 방법의 시간 복잡도는 어떻게 될까요? 전체 물건의 개수를 T라고 하면, T는 모든 K의 합입니다. 최악의 경우 T는 N * 10,000 = 1,000,000에 달할 수 있습니다. 0-1 배낭 알고리즘은 O(T * M)의 시간 복잡도를 가지므로, 1,000,000 * 10,000 = 10,000,000,000번의 연산이 필요합니다. 이는 약 100억 번의 연산으로, 일반적인 환경에서 제한 시간 내에 실행하기 어렵습니다.

문제의 본질: 중복 계산

왜 이렇게 느릴까요? 핵심은 불필요한 중복에 있습니다. 같은 물건 5개를 각각 독립적으로 처리하면서, 우리는 동일한 선택지를 반복적으로 고려하게 됩니다. 예를 들어, “이 물건 3개를 선택한다”는 결정을 내리기 위해, 알고리즘은 첫 번째 물건 선택, 두 번째 물건 선택, 세 번째 물건 선택을 각각 독립적으로 평가합니다. 이는 근본적으로 비효율적입니다.

💡 핵심 통찰: 이진 분해(Binary Decomposition)

효율의 필요성

순진한 방법이 실패한 이유는 명확합니다: 물건의 총 개수가 너무 많아집니다. 그렇다면 물건의 개수를 줄이면서도 모든 가능한 선택을 표현할 수 있는 방법이 있을까요?

여기서 이진 표현(Binary Representation)의 힘이 드러납니다. 우리가 컴퓨터에서 모든 숫자를 2의 거듭제곱의 합으로 표현할 수 있듯이, K개의 물건을 선택하는 모든 경우를 더 적은 수의 “묶음”으로 표현할 수 있습니다.

이진 분해의 원리

예를 들어, 어떤 물건이 13개 있다고 가정해봅시다. 순진한 방법은 이를 13개의 독립적인 물건으로 취급합니다. 하지만 우리는 0부터 13까지의 모든 수를 다음과 같은 묶음으로 표현할 수 있습니다:

  • 1개짜리 묶음 (무게 V*1, 만족도 C*1)
  • 2개짜리 묶음 (무게 V*2, 만족도 C*2)
  • 4개짜리 묶음 (무게 V*4, 만족도 C*4)
  • 6개짜리 묶음 (무게 V*6, 만족도 C*6)

왜 이렇게 나눌까요? 1 + 2 + 4 = 7이므로, 처음 세 묶음만으로 0부터 7까지의 모든 수를 만들 수 있습니다(각 묶음을 선택하거나 선택하지 않음으로써). 남은 13 - 7 = 6개는 마지막 묶음으로 추가하면, 0부터 13까지의 모든 수를 정확히 표현할 수 있습니다.

📘 About Binary Decomposition
이진 분해는 K개의 동일한 물건을 O(log K)개의 묶음으로 변환하는 기법입니다. 핵심은 2의 거듭제곱(1, 2, 4, 8, ...)을 사용하여 0부터 K까지의 모든 정수를 표현할 수 있다는 점입니다. 각 묶음은 0-1 배낭 문제에서 하나의 물건처럼 취급되며, 이를 통해 시간 복잡도를 극적으로 개선할 수 있습니다.

왜 이것이 효과적인가?

이진 분해를 사용하면, K개의 물건을 O(log K)개의 묶음으로 변환할 수 있습니다. 예를 들어, K = 10,000인 경우, 순진한 방법은 10,000개의 물건을 처리하지만, 이진 분해는 약 14개의 묶음만 생성합니다(log₂(10,000) ≈ 13.3).

전체 시간 복잡도는 어떻게 될까요? 각 물건 종류를 이진 분해하면 최대 O(N * log(max K)) 개의 묶음이 생성됩니다. 최악의 경우 N = 100, log(10,000) ≈ 14이므로 약 1,400개의 묶음이 생성됩니다. 0-1 배낭 알고리즘을 적용하면 1,400 * 10,000 = 14,000,000번의 연산으로, 100억에서 1,400만으로 약 700배 개선됩니다.

구현 전략

이진 분해를 구현할 때는 다음 과정을 따릅니다:

  1. a = 1로 시작하여, sum + a ≤ K인 동안 a개짜리 묶음을 추가합니다
  2. 각 반복마다 a를 두 배로 증가시킵니다(a <<= 1)
  3. 루프가 끝나면 남은 개수를 마지막 묶음으로 추가합니다

이렇게 하면 2의 거듭제곱과 나머지를 정확히 분리하여, 0부터 K까지의 모든 수를 표현할 수 있는 최소 묶음 집합을 얻습니다.

🔍 알고리즘 실행 과정

구체적인 예시로 알고리즘의 동작을 살펴보겠습니다.

2 10
3 4 5
2 5 3

이는 두 종류의 물건이 있고, 가방의 최대 무게는 10kg이라는 의미입니다:

  • 물건 1: 무게 3kg, 만족도 4, 개수 5개
  • 물건 2: 무게 2kg, 만족도 5, 개수 3개

Phase 1: 이진 분해

물건 1 (V=3, C=4, K=5)

초기 상태: a = 1, sum = 0, K = 5

  • 반복 1: sum + 1 = 1 ≤ 5 → 묶음 추가: (3*1, 4*1) = (3, 4), sum = 1, a = 2
  • 반복 2: sum + 2 = 3 ≤ 5 → 묶음 추가: (3*2, 4*2) = (6, 8), sum = 3, a = 4
  • 반복 3: sum + 4 = 7 > 5 → 종료
  • 남은 개수: K - sum = 5 - 3 = 2 → 묶음 추가: (3*2, 4*2) = (6, 8)

결과: [(3, 4), (6, 8), (6, 8)]

물건 2 (V=2, C=5, K=3)

초기 상태: a = 1, sum = 0, K = 3

  • 반복 1: sum + 1 = 1 ≤ 3 → 묶음 추가: (2*1, 5*1) = (2, 5), sum = 1, a = 2
  • 반복 2: sum + 2 = 3 ≤ 3 → 묶음 추가: (2*2, 5*2) = (4, 10), sum = 3, a = 4
  • 반복 3: sum + 4 = 7 > 3 → 종료
  • 남은 개수: K - sum = 3 - 3 = 0 → 추가 없음

결과: [(2, 5), (4, 10)]

전체 묶음 배열: [(3, 4), (6, 8), (6, 8), (2, 5), (4, 10)]

Phase 2: 동적 프로그래밍

이제 5개의 묶음에 대해 0-1 배낭 알고리즘을 적용합니다. dp[j]는 무게 j일 때의 최대 만족도를 나타냅니다.

초기 상태: dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

묶음 1: (3, 4)

  • j=10: dp[10] = max(0, dp[7]+4) = max(0, 4) = 4
  • j=9: dp[9] = max(0, dp[6]+4) = 4
  • j=8: dp[8] = max(0, dp[5]+4) = 4
  • j=7: dp[7] = max(0, dp[4]+4) = 4
  • j=6: dp[6] = max(0, dp[3]+4) = 4
  • j=5: dp[5] = max(0, dp[2]+4) = 4
  • j=4: dp[4] = max(0, dp[1]+4) = 4
  • j=3: dp[3] = max(0, dp[0]+4) = 4

상태: dp = [0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4]

묶음 2: (6, 8)

  • j=10: dp[10] = max(4, dp[4]+8) = max(4, 12) = 12
  • j=9: dp[9] = max(4, dp[3]+8) = max(4, 12) = 12
  • j=8: dp[8] = max(4, dp[2]+8) = max(4, 8) = 8
  • j=7: dp[7] = max(4, dp[1]+8) = max(4, 8) = 8
  • j=6: dp[6] = max(4, dp[0]+8) = max(4, 8) = 8

상태: dp = [0, 0, 0, 4, 4, 4, 8, 8, 8, 12, 12]

묶음 3: (6, 8) (동일 과정 반복)

상태: dp = [0, 0, 0, 4, 4, 4, 8, 8, 8, 12, 16]

묶음 4: (2, 5)

  • j=10: dp[10] = max(16, dp[8]+5) = max(16, 13) = 16
  • j=9: dp[9] = max(12, dp[7]+5) = max(12, 13) = 13
  • j=8: dp[8] = max(8, dp[6]+5) = max(8, 13) = 13
  • j=7: dp[7] = max(8, dp[5]+5) = max(8, 9) = 9
  • j=6: dp[6] = max(8, dp[4]+5) = max(8, 9) = 9
  • j=5: dp[5] = max(4, dp[3]+5) = max(4, 9) = 9
  • j=4: dp[4] = max(4, dp[2]+5) = max(4, 5) = 5
  • j=3: dp[3] = max(4, dp[1]+5) = max(4, 5) = 5
  • j=2: dp[2] = max(0, dp[0]+5) = 5

상태: dp = [0, 0, 5, 5, 5, 9, 9, 9, 13, 13, 16]

묶음 5: (4, 10)

  • j=10: dp[10] = max(16, dp[6]+10) = max(16, 19) = 19
  • j=9: dp[9] = max(13, dp[5]+10) = max(13, 19) = 19
  • j=8: dp[8] = max(13, dp[4]+10) = max(13, 15) = 15
  • j=7: dp[7] = max(9, dp[3]+10) = max(9, 15) = 15
  • j=6: dp[6] = max(9, dp[2]+10) = max(9, 15) = 15
  • j=5: dp[5] = max(9, dp[1]+10) = max(9, 10) = 10
  • j=4: dp[4] = max(5, dp[0]+10) = max(5, 10) = 10

최종 상태: dp = [0, 0, 5, 5, 10, 10, 15, 15, 15, 19, 19]

최대 만족도: 19

💻 Source Code

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 200000

int N, M, V, C, K;

int main()
{
   <em>// 입출력 속도 최적화</em>
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   
   <em>// N: 물건 종류의 수, M: 가방의 최대 무게</em>
   cin >> N >> M;
   
   <em>// A: 이진 분해된 묶음들을 저장하는 배열</em>
   <em>// 각 원소는 (무게, 만족도) 쌍</em>
   vector<pair<int,int>> A;
   
   <em>// 각 물건 종류에 대해 이진 분해 수행</em>
   for (int i = 0; i < N; ++i) {
      <em>// V: 물건 하나의 무게</em>
      <em>// C: 물건 하나의 만족도</em>
      <em>// K: 이 물건의 개수</em>
      cin >> V >> C >> K;
      
      <em>// 이진 분해 알고리즘</em>
      <em>// a: 현재 묶음의 크기 (1, 2, 4, 8, ...)</em>
      <em>// sum: 지금까지 묶음으로 만든 물건의 총 개수</em>
      int a = 1, sum = 0;
      
      <em>// 2의 거듭제곱 묶음들을 생성</em>
      <em>// sum + a <= K 조건: 남은 물건이 현재 묶음 크기 이상일 때만 추가</em>
      while(sum + a <= K) {
         <em>// a개짜리 묶음 추가: 무게 V*a, 만족도 C*a</em>
         A.push_back(make_pair(V*a, C*a));
         sum += a;  <em>// 지금까지 처리한 물건 개수 갱신</em>
         a <<= 1;   <em>// 다음 묶음 크기는 현재의 2배 (비트 시프트 연산)</em>
      }
      
      <em>// 남은 물건들을 마지막 묶음으로 추가</em>
      K -= sum;  <em>// 아직 묶음으로 만들지 않은 물건의 개수</em>
      if (K) {
         <em>// 남은 K개를 하나의 묶음으로 추가</em>
         A.push_back(make_pair(V*K, C*K));
      }
   }
   
   <em>// 동적 프로그래밍 배열</em>
   <em>// dp[j]: 정확히 무게 j를 사용했을 때 얻을 수 있는 최대 만족도</em>
   <em>// long long 사용 이유: 최대 만족도가 int 범위를 초과할 수 있음</em>
   vector<long long> dp(M+1, 0);
   
   <em>// 각 묶음에 대해 0-1 배낭 알고리즘 적용</em>
   for (int i = 0; i < A.size(); ++i) {
      <em>// 현재 묶음의 무게와 만족도 추출</em>
      tie(V,C) = A[i];
      
      <em>// 역순으로 순회하는 이유:</em>
      <em>// 같은 묶음을 중복으로 선택하지 않기 위함</em>
      <em>// 순방향으로 순회하면 dp[j-V]가 이미 이번 묶음을 포함한 값이 될 수 있음</em>
      for (int j = M; j >= 0; --j) {
         <em>// 현재 무게 j에서 묶음 V를 뺄 수 있는지 확인</em>
         if (j-V >= 0) {
            <em>// dp[j] 갱신: 묶음을 선택하지 않은 경우 vs 선택한 경우</em>
            <em>// dp[j-V] + C: 무게 j-V에서 최적값 + 현재 묶음의 만족도</em>
            dp[j] = max(dp[j], dp[j-V]+C);
         }
      }
   }
   
   <em>// 모든 무게에 대해 최대 만족도 찾기</em>
   <em>// 정확히 M을 사용하지 않아도 되므로, 0부터 M까지 모두 확인</em>
   long long ans = 0LL;
   for (int i = 0; i <= M; ++i) {
      ans = max(ans, dp[i]);
   }
   
   <em>// 최대 만족도 출력</em>
   cout << ans << "\n";
   
   return 0;
}

🔁 Alternative Approach: 공간 최적화

위 구현은 이미 공간 복잡도 O(M)을 달성했지만, 만약 메모리가 극도로 제한적인 환경이라면 슬라이딩 윈도우 기법을 사용할 수도 있습니다. 하지만 이 문제의 제약 조건 하에서는 현재 구현이 가장 실용적이고 직관적입니다.

또 다른 접근법은 각 물건에 대해 완전 배낭(Unbounded Knapsack) 알고리즘을 적용하되, 선택 횟수를 K로 제한하는 것입니다. 그러나 이는 구현이 복잡하고 시간 복잡도가 O(N * M * max K)로 증가하여 비효율적입니다.

📌 Summary and Key Takeaways

이 문제는 Bounded Knapsack(유한 배낭) 문제의 전형적인 예시로, 단순히 모든 물건을 펼쳐놓는 접근법이 시간 제약으로 인해 실패하는 상황을 보여줍니다. 핵심은 이진 분해(Binary Decomposition) 기법을 통해 K개의 동일한 물건을 O(log K)개의 묶음으로 변환하는 것이었습니다.

이 기법이 효과적인 이유는 2의 거듭제곱의 조합으로 0부터 K까지의 모든 정수를 표현할 수 있다는 수학적 사실에 기반하기 때문입니다. 이를 통해 물건의 총 개수를 극적으로 줄여 시간 복잡도를 O(N * M * K)에서 O(N * log K * M)으로 개선할 수 있었습니다.

또한, 동적 프로그래밍 단계에서 역순 순회를 통해 중복 선택을 방지하는 0-1 배낭 패턴을 정확히 적용하는 것이 중요했습니다. 이는 같은 묶음을 여러 번 사용하지 않도록 보장하며, 각 묶음이 독립적인 선택 대상이 되도록 합니다.

Similar Posts