백준 12920. 평범한 배낭 2

🅰 백준 12920. 평범한 배낭 2

12920번: 평범한 배낭 2

✏️ 문제 풀이

• 평범한 배낭문제와 비슷하지만 다른점은 "한 물건을 두개 이상 챙기는 것도 가능하다." 이 부분이다.
• 처음 이 부분을 해결하기 위해 물건이 2개이상 있는 경우에는 for문을 이용하여 2개,3개,4개...k개 만큼을 넣었을 때의 가치를 비교하여 최적의 가치를 찾아서 제출했다
• 하지만 6%때 시간초과가 떠서 최악의 경우를 생각해보니 가방의 무게가 10,000이고 100개의 물품이 물품당 10,000개씩있다면 100 * 10000 * 10000 = 100000000000 시간초과가 날만했다.. 
• 시간복잡도는 O(N*K*M) 이였다. 

 

  -  따라서 최적화가 필요했다.

  -  배낭문제는 물건들을 넣을때 마다 모든 케이스를 비교하여 현재 최적의 값을 넣기 때문에 중복되는 계산 부분을

     방지하기 위해 물품을 2의 제곱수의 합으로 분할하는 기법을 사용하여 물건의 수를 줄여주는 것이 핵심이다.

 

만약 입력 데이터가 

2 3 2 7 1  1 9 3

N = 2(물건의 개수), M = 3(민호가 들수있는 최대무게)

1. 일단 물건들을 2의 제곱수 합으로 바꿔줘야한다. 2 7 1은 1개만 있으므로 일단 pass하고

2. V = 1(물건의 무게) C = 9(만족도, 가치) K = 3(물건의 개수) 을 아래 2의 제곱수 합으로 바꾸는 식에 대입해보자

for (int j = 0; count > 0; j++) { // bitmasking을 이용하여 저장,       int tmp = Math.min(1 << j, count);      int curWeight = weight * tmp;      int curHappy = happy * tmp;      product.add(new int[] { curWeight, curHappy });      count -= tmp; }

j를 0부터 시작해서(2^0부터 시작) count(물건의 개수)가 0이될때까지 반복한다.

int tmp = Math.min(1<<j, count) 부분이 필요한 이유는 모든 수가 15(1,2,4,8) 처럼 딱 떨어지면 괜찮은데 

물건의 개수인 K를 무조건적으로 2의 제곱수의 합으로만 바꿔주면 만약 int tmp = (1<<j) 13이면 (1,2,4,8)이 되는데

이렇게 되면 모든 수의 합이 13보다 큰 15까지 될 수 있기 때문에

만약 count가 1<<j보다 작으면 count(남은 수)를 넣어주면 (1,2,4,6)이 되서

1, 2, 3(1+2), 4, 5(1+4), 6, 7(1+6), 8(2+6), 9(1+2+6), 10(4+6), 11(1+4+6), 12(2+4+6), 13(1+2+4+6)이 되어서

모든 경우의 수를 더해도 13까지 나오기 때문에 Math.min(1<<j, count) 이 부분이 필요하다.

 

즉 1~13의 13가지 수를 1,2,4,6 4가지의 물건으로 만들어서 13가지를 넣는 모든 경우의 수를 계산하여서 최적화 시키는 방법이다. 

 

3. 다시 입력데이터를 식에 대입해보면 for문을 2번 반복하여 물품은 3개 에서 1(value : 9), 2(value : 18) 2개가 나온다.

   즉 이를 가방에 넣는다 하면 1, 2, 3(1+2)가 되기 때문에 물품 3개를 모두 넣을 수 있는 방법이 되는것이다.  

 

4. 이와 마찬가지로 모든 물품을 2의 제곱수 합으로 계산한 뒤 ArrayList에 (무게, 가치)를 계산해서 따로 저장을 해서

   마지막으로는 평범한 배낭1 문제와 같이 ArrayList에 저장된 물품의 수만큼 dp를 돌려주었다.

 

이렇게 되면 시간복잡도가 O(N*log(K)*M)가 되어서 문제를 통과할 수 있다.

 

 

  -  아래는 이 과정에 대해 백준에서 설명을 잘 해주신 분의 답을 가져와봤다. 내 설명이 이해가 잘 안간다면 아래도

     한번 읽어보길 바란다

물건이 C개 있다면, 이것을 1개짜리, 2개짜리, 4개짜리, 8개짜리, ... 묶음 판매 상품으로 만들고, 각 상품이 1개씩만 있다고 가정하여 문제를 변형하는 과정입니다. 예를 들어, 어떤 물건이 15개 존재하고 가치가 3이라면, 이를 가치 3, 6, 12, 24를 가지는 상품으로 분할해 각각이 하나씩만 있는 것으로 바꾸어 개수 조건을 없앱니다. 이 경우, 만약 한 개 살 예정이었다면 3짜리를, 두 개 살 예정이었다면 6짜리를, 세 개 살 예정이었다면 3짜리와 6짜리를, ... , 15개 다 살 예정이었다면 3, 6, 12, 24짜리를 모두 구매하는 것과 동치이고, 이러한 구매가 항상 가능함이 보장됩니다. (이진수로 생각해보세요) 이렇게 바꾸고 나면 개수를 무시한 채로(모든 물건이 1개가 되었으므로) 평범한 디피 문제로 바꾸어 풀 수 있습니다.

 

✏️ 소스코드

package dp;

import java.util.*;
import java.io.*;

public class Main_플레4_12920_평범한배낭2 {
	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());
		int kg = Integer.parseInt(st.nextToken());
		ArrayList<int[]> product = new ArrayList<>();
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			int happy = Integer.parseInt(st.nextToken());
			int count = Integer.parseInt(st.nextToken());
			for (int j = 0; count > 0; j++) {		// bitmasking을 이용하여 저장, 
				int tmp = Math.min(1 << j, count);
				int curWeight = weight * tmp;
				int curHappy = happy * tmp;
				product.add(new int[] { curWeight, curHappy });
				count -= tmp;
			}
		}
		int curN = product.size();
		int dp[][] = new int[curN+1][kg + 1];
		for (int i = 1; i <= curN; i++) {			// 배낭문제랑 똑같이 dp돌림
			for (int j = 1; j <= kg; j++) {
				if (j >= product.get(i-1)[0]) {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - product.get(i-1)[0]] + product.get(i-1)[1]);
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		System.out.println(dp[curN][kg]);
	}
}

 

✅ 후기

• 정말 쉽게 생각했는데 괜히 플레4가 아니라는 생각이 들었다. 하지만 2의 제곱수를 사용하는 방법도 알았고, 이와 비슷한 문제가 나왔을 때 새로운 관점으로 접근할 수 있을거라는 자신감이 생겼다.