문제 링크 - 문제 12920번
동적프로그래밍 문제들을 플다가 knapsack 문제들을 마주하게 되었다. 나는 1/0, unbounded knapsack 까지만 배웠다. 문제 12865번이 전형적인 1/0 knapsack 이었는데, 이게 골드5였다. 그러고나서 배낭을 키워드로 검색해서 unbounded(무제한) knapsack도 풀어야지 하고 생각했는데 어라? 이게 플레티넘 4문제? 이게 그렇게 난이도 차이가 크나? 오 ㅋㅋ solved 티어 개꿀이겠는데? 하면서 문제 풀이를 했다. 그런데 이건 무제한가방문제보다 한 단계 더 업그레이드 된 문제였다.... bounded knapsack이라는 문제였다. 어찌저찌 우격다짐으로 풀이를 했다. 답도 잘나온거 같아. 근데 오우 시간초과가 나왔다. 어? 뭐지? 분명 dp도 잘 적용이 됫는데 시간초과가 나오면....? 뭐 어쩌라는거야?? 그래서 gpt 슨상님께 물어보았다. 물어보니 이진분할이라는 반복문 최적화를 해야된다더라... 음 대충 이런거구나 하고 풀이는 성공했는데, 아직 내 머리속에서 자유롭게 만져지는 수준은 아니라서 기록을 해둬야겠다....
처음 이 방법을 봤을 땐 굉장히 뜬금없었다. 먼저 이진 분해는 “유한 개수(K)”를 0/1 아이템으로 바꾸는 최적화이다. 그리고 모든 가능한 사용 개수를 정확히 표현할 수 있기 때문에 항상 정답이 된다.
엄 잘 모르겠다 뭐라는거지?
🔥 1. 왜 내가 만든 bounded knapsack(개수 제한 DP)이 느린가?
예를 들어 물건이 이렇게 있다고 하자:
무게: w
가치: v
개수: K = 13정석적 구현은 이렇게 생겼다 - 내가 풀이한거:
for (c = 1 to K) // 여기서 시간 폭발
dp[w][...] = max(dp[w], dp[w - c*w] + c*v);즉, “이 물건을 0개~13개 써볼까?” K번 반복함.
K가 크면 DP가 심각하게 느려진다.
🔥 2. 이때 반복을 줄이기 위한 아이디어 - “이진 분할”
핵심 발상:
“한 번에 1개만 시도하지 말고, ‘2^i 개씩 묶어서’ 시도하면 되지 않을까?”
왜 2^i인가?
- 1 + 2 + 4 + 8 + … 은 모든 자연수 조합을 정확히 표현할 수 있기 때문
- 즉, 0개~K개까지의 모든 경우를 구현 가능
13개 예시:
13 = 1 + 2 + 4 + 6이 4개의 묶음으로 0~13개의 모든 선택을 표현할 수 있다.
🔥 3. 정말로 “모든 경우를 표현”할 수 있을까?
▷ 비교 : 기존 방식
한 물건을 c개 사용하는 경우, c는 0~13 모두 가능해야 함.
▷ 이진 분해 방식
가짜 물건(묶음)을 이렇게 만든다:
| 묶음 | 의미 | 무게 | 가치 |
|---|---|---|---|
| A | 1개 묶음 | 1w | 1v |
| B | 2개 묶음 | 2w | 2v |
| C | 4개 묶음 | 4w | 4v |
| D | 6개 묶음 | 6w | 6v |
이제 이 4개 아이템을 0/1 배낭처럼 사용하면:
- 0개 사용 → 0
- A만 → 1
- B만 → 2
- A+B → 3
- C → 4
- A+C → 5
- B+C → 6
- A+B+C → 7
- D → 6
- A+D → 7
- B+D → 8
- …
- A+B+C+D → 13
즉, 0~13까지 모든 개수를 정확하게 표현 가능.
이게 가능한 이유는:
“모든 정수는 이진수로 표현할 수 있다”
라는 아주 기본적인 사실 때문.
그래서 이진 분해는 정확한 방법이며, 절대로 정답을 잃지 않는다.
🔥 4. 그럼 왜 점프해서 '2의 거듭제곱'을 쓰는가?
1부터 하나씩 써보면 O(K) 반복인데,
2^i로 묶어서 “큰 단위로 점프”하면 묶음 개수가 log(K)개가 된다.
예)
| K | 이진 분해 후 묶음 개수 |
|---|---|
| 13 | 4개 |
| 100 | 7개 |
| 1000 | 10개 |
| 1,000,000 | 20개 |
즉,
DP 계산량이 K에서 log(K)로 줄어든다.
→ 엄청난 성능 개선.
🔥 5. “그럼 이진 분해는 도대체 언제 쓰냐?”
질문이 아주 정확함.
👉 조건 1: 개수 제한이 있음 (bounded)
- 무한이면 필요 없음
- 0/1이면 필요 없음
- 개수가 크고 제한이 있을 때만 의미 있음
👉 조건 2: K가 크다
- K가 10 이하 → 필요 없음
- K가 수백~수천 → 필수
- K가 수만~수십만 → 없으면 무조건 시간초과
👉 조건 3: DP 용량 M이 크며, N·M·K가 터질 가능성이 높을 때
백준 12920이 이 케이스.
🔥 6. 뜬금없는 기법처럼 느껴지는 이유
나는 지금까지:
- 0/1 배낭
- 무한 배낭
- 유한 배낭
까지는 배웠는데,
“유한 배낭을 ‘0/1 여러 개’로 변환한다”
라는 구조적 발상을 본 적이 없기 때문이다.
하지만 흐름만 이해하면 절대 어려운 게 아니다. - 어려웠다. 사실 지금도 뭔가 직관적으로 닿지 않아... 수학적인 생각을 해야되는데 수학적인 머리가 굳었나봐.... 20년만 젊었어도....
유한 개수의 물건을 → 여러 개의 0/1 묶음으로 바꿔서 → 0/1 DP로 해결하는 전략
이게 이진 분해의 전부다.
🔥 7. 직관적으로 더 쉽게 말하면
13개의 아이템이 있을 때,
13번 반복하는 대신,
“큰 덩어리로 묶어서 4번만 반복하는 꼼수”
라고 생각하면 된다.
🔥 8. 궁금했던 핵심 정리
❓ 뜬금없는데 왜 갑자기 2진수?
➡ “모든 숫자는 2진수 묶음(1,2,4,8…)의 합으로 표현 가능하기 때문”
❓ 이렇게 하면 원래 DP 조건이 망가지지 않나?
➡ 안 망가짐. 0~K개의 모든 선택이 여전히 표현됨.
❓ 어떤 상황에 써야 하는가?
➡ bounded + K가 클 때 = 이진 분해 필수
➡ 백준 12920처럼 N·M·K가 크면 반드시 필요
❓ 고급 알고리즘인가?
➡ 없음. 그냥 단순한 반복문 최적화 기법임.
