백준 BOJ 12920 - 평범한 배낭 2

약간의 두뇌가 가미된 배낭문제

기본적인 구조는 12865번 평범한 배낭과 동일하다.

 

www.acmicpc.net/problem/12920

12920번: 평범한 배낭 2

먼저 딱 보고 생각한 것은

O(KNM)인데, 이렇게 되면 당연하겠지만 TLE가 나온다.

O(KNM)은

N개의 물건에 대해서 1~K갯수가 있을텐데, 각각의 개수를 모두

"K배 더 무겁고 K배 가치가 더 나가는 물건" 으로 바꿔주면 쉽게 나온다.

 

AC는 O(NlogKM) 으로 받았는데,

K를 log2(K)로 바꿔주는게 이 문제의 핵심이 되겠다.

 

위의 KNM풀이의 함정은 X배 무거운 물건을 챙기는 경우가

중복된다는데에 있다.

ex) 5배 무거운 물건은 1배 + 4배, 2배 + 3배, 5배 의 조합으로 가능하다.

이렇게 생기는 중복을 최대한 없애주기 위해서는

1, 2, 4, 8, 즉 이진수처럼 2의 제곱수 배들만 남겨주면 깔끔해진다.

가장 큰 2의 제곱수를 X라 할때,

2의 제곱수 배들만 이용한다면 2X-1까지의 모든 수들의 합을 만들어 낼 수 있고,

 

2의 제곱수 배들로 K를 분할하면 남는 수가 하나 생기는데,

이 수까지 처리해준다면 AC가 나온다.

 

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

vector<int> w;
vector<int> v;

int dp[2345][12345] = {0};

int main(){
	int n,m;
	int a,b,c;
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++){
		scanf("%d %d %d", &a, &b, &c);
		for(int j=0; c>0; j++){
			int tmp = min(1<<j, c);
			w.push_back(a*tmp);
			v.push_back(b*tmp);
			c-=tmp;
		}
	}
	
	for(int i=1; i<=w.size(); i++){
		for(int j=1; j<=m; j++){
			if(j>=w[i-1]) dp[i][j] = max(dp[i-1][j-w[i-1]] + v[i-1] , dp[i-1][j]);
			else          dp[i][j] = dp[i-1][j];
		}
	}
	
	printf("%d", dp[w.size()][m]);
	return 0;
}

해답을 뇌속에서 어느정도 알고있었음에도

구현에서 이상하리만치 오래걸렸던 문제.

좀 더 풀어야할듯....