BOJ 백준 12920 평범한 배낭 2

kyjdummy 2025. 4. 8. 20:27

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

[ 문제 요약 ]

일반 배낭 문제와 비슷하지만, 한 상품을 K 번 내에서 원하는 만큼 선택이 가능하다는 것이 다릅니다.

[ 테스트 케이스 설명 ]

최대 무게를 넘기지 않게 물건을 담을 때 최대 만족도 출력
2 3		// 물건 종류의수 N(1<=100),가방의 최대 무게 M(1<=10,000)
2 7 1	// 물건 무게 V(1<=M), 만족도 C(1<=10,000),물건 개수 K(1<=10,000) / 1<= V*K<= 10,000)
1 9 3
답 : 27

[ 문제 풀이 ]

이 문제는 배낭 문제의 개념을 이해하고, 그에 따른 풀이 방법을 알면 쉽게 풀 수 있습니다.

배낭 문제는 크게 3종류가 있습니다. 다중 배낭 문제, 무한 배낭 문제, 0/1배낭 문제가 있습니다.

0/1 배낭 문제 : 하나의 상품을 한 번만 선택할 수 있음
무한 배낭 문제 : 한 물건을 원하는 만큼(무한히) 반복해서 선택할 수 있음
다중 배낭 문제 : 한 물건을 정해진 개수(cnt) 만큼 선택할 수 있음

현재 이 문제는 다중 배낭 문제이며, 다중 배낭 문제를 [이진 분할 기법]을 이용해 0/1배낭 문제로 바꿔 풀 수 있습니다.

즉, 다중 배낭 문제를 0/1배낭 문제로 풀 수 있도록 구조를 바꿔, 0/1배낭 문제로 푸는 것입니다.

[이진 분할 기법]은, 품목당 선택을 K개 할 수 있다면 K 개를 1,2,4,8,16… 과같이 이진 증감 형태로 분할해 묶음으로 묶어 분할해 푸는 것입니다.

즉, K 개 선택을 여러 개의 덩어리로 쪼개는 것인데, 그 쪼개는 방법이 이진수 증가 형태로 쪼개는 것입니다.

예를 들어 선택 가능 횟수가 14라고 하면, 묶음을 1개, 2개, 4개, 7개로 묶는 것입니다.

여기서 7이 나온 이유는 1,2,4…로 분할해 나가다가 이진수가 커져서 남은 선택을 초과할 때, 즉, 묶지 못할 때 남은 나머지를 의미합니다.

다시 설명하면,

K를 14개 선택하는 것을 변경하여,

1개 선택한 경우를 하나의 가치와 하나의 무게로 만들고,

2개 선택한 경우를 하나의 가치와 하나의 무게로 만들고,

4개 선택한 경우를 하나의 가치와 하나의 무게로 만들고,

7개 선택한 경우를 하나의 가치와 하나의 무게로 만듭니다.

그럼 1 + 2 + 4 + 7 = 14가 되는 꼴입니다.

이게 정답이 나와?라는 질문이 생깁니다. 먼저 아래 정답 코드를 보고 이진 분할에 대해 추가 설명하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());// 물건 종류의수 N(1<=100)
		int M = Integer.parseInt(st.nextToken());// 가방의 최대 무게 M(1<=10,000)
		List<Integer> W = new ArrayList<>();// 무게
		List<Integer> V = new ArrayList<>();// 가치
		for(int i=0; i<N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());// 물건 무게 V(1<=M)
			int c = Integer.parseInt(st.nextToken());// 만족도 C(1<=10,000)
			int k = Integer.parseInt(st.nextToken());// 물건 개수 K(1<=10,000) / 1<= V*K<= 10,000)
			
			int cnt = 1;	// 이진 분할 플레그
			// 남은 선택개수(K)가 이진 분할 플레그보다 작거나 같을 때 계속 반복
			while(cnt <= k)
			{
				W.add(cnt * v);// 무게
				V.add(cnt * c);// 가치
				k -= cnt;// 선택개수 감소
				cnt <<= 1;// 이진 분할 플레그 2배 증가
			}
			// 이진 분할을 못하는 나머지도 하나의 묶음으로 만듬
			if(k != 0)
			{
				W.add(k * v);// 무게
				V.add(k * c);// 가치
			}
		}
		
		// 이하 코드는 단순 0/1 배낭문제의 1차원 배열 풀이 입니다.
		int dp[] = new int[M + 1];
		
		for(int i=0; i<W.size(); i++)
		{
			int nowWeight = W.get(i);
			int nowValue = V.get(i);
			
			for(int j=M; j>=nowWeight; j--)
			{
				dp[j] = Math.max(dp[j], dp[j-nowWeight] + nowValue);
			}
		}
		System.out.print(dp[M]);
	}
}

[ 이진 분할 설명 ]

그러면 숫자를 위와 같이 이진 분할 했을 때 결과가 정해라는 것을 어떻게 증명할 것이냐?

라는 질문을 할 수 있습니다. 아래는 그 설명입니다.

기준 숫자가 20일 경우, 20을 이진 분할하고 나머지 숫자를 구하면 아래와 같습니다.

[ 1, 2, 4, 8 / 나머지 5 => 총합 20 ]

20을 이진 분할해 얻은 숫자는 모두 1, 2, 4, 5, 8입니다.( 해당 숫자를 모두 더하면 20임 )

이 숫자 [ 1, 2, 4, 5, 8 ]을 통해 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20을 모두 만들 수 있어야 합니다.

아래를 보면 20을 분할해서 만든 1, 2, 4, 5, 8을 통해 1부터 20사이 모든 숫자를 만들 수 있습니다.

1 = 1
2 = 2
3 = 1+ 2
4 = 4
5 = 5
6 = 5 + 1
7 = 5 + 2
8 = 8
9 = 8 + 1
10= 8 + 2
11 = 8 + 2 + 1
12 = 8 + 4
13 = 8 + 5
14 = 8 + 5 + 1
15 = 8 + 5 + 2
16 = 8 + 5 + 2 +1
17 = 8 + 5 + 4
18 = 8 + 5 + 4 + 1
19 = 8 + 5 + 4 + 2
20 = 8 + 5 + 4 + 2 + 1

위와 같이 분할한 데이터들을 통해 모든 경우의 수 조합이 가능하기 때문에 [정답 코드]가 정상 작동합니다.

이진 분할은 수학적으로 모든 수를 2의 거듭제곱들의 합으로 표현할 수 있다는 원리에 기반하며,

이를 통해 다중 물건을 0/1 물건으로 이진 분할해도 원래 문제와 동일한 해를 구할 수 있음을 알 수 있습니다.

[ 이진 분할 이해 TIP ]

이진 분할 시 이진수 관점에서 보면 아래와 같습니다.

0001
0010
0100
1000

모든 자릿수마다 1이 있기 때문에 각 조합을 통해 0000부터 1111까지 모든 수를 만들 수 있습니다.