백준 1450 냅색문제

https://www.acmicpc.net/problem/1450

1450번: 냅색문제

 

 

EXPLANATION

 

일단 최대 무게에 제한이 없다고 생각하고 주어진 N개의 물건을 가방에 넣는 경우를 구한다.

그리고 최대 무게 이하인 것들만 골라내면 된다.

 

각 각의 물건에 대해서 '가방에 넣는다'와 '가방에 넣지 않는다'로 2개의 경우가 생긴다.

따라서, 무게 제한없이 N개의 물건을 가방에 넣는 각 각의 다른 케이스를 구하려면 2^N번 선택해야 한다. (경우의 수: 2^N)

그런데, 물건의 최대 개수는 30이고 2^30은 10억 7천만이므로 시간 초과가 발생한다.

따라서, 원소의 갯수(물건의 갯수)가 비슷한 크기의 두 개의 집합으로 물건을 분리한 후 각 두 집합의 물건에 대해서 가방에 넣는 경우의 수를 구한다.

이후, 첫번째 집합에서 구한 모든 경우의 무게에 대해서 각 각 두번째 집합에서 구한 모든 경우의 무게를 오름차순으로 정렬 한 후 더해서 배열을 만든다.

그럼 이 각 각의 배열에서 처음 무게부터 최대 무게를 넘지 않는 첫번째 무게까지의 갯수를 세면 된다.

이는 upper_bound함수를 이용해 이분탐색으로 찾아낼 수 있다.

이 각 각의 배열에서 구한 갯수들의 총합이 답이다.

 

총 시간 복잡도: O ( 2^(N/2) * log(2^(N/2)) ) => O( (2^(N/2)) * N )

 

 

위의 풀이를 예를 들어서 설명하면,

예제 입력이 아래와 같을 때,

4 6
4 3 2 1

물건의 갯수 N이 4개 이므로,

원소의 크기가 같은 두 집합 {4, 3}과 {2, 1}으로 물건을 분리한다.

첫번째 집합에서 구한 모든 경우의 무게는 [4], [3], [0], [7] 이다.

두번째 집하벵서 구한 모든 경우의 무게는 [2], [1], [0], [3] 이고, 이를 오름차순하면 [0], [1], [2], [3] 이다.

첫번째 집합에서 구한 모든 경우의 무게에 대해서 각 각 두번째 집합에서 구한 모든 경우의 무게를 오름차순으로 정렬한 후 더한 배열들은

[0 + 4], [1 + 4], [2 + 4], [3 + 4],

[0 + 3], [1 + 3], [2 + 3], [3 + 3],

[0 + 0], [1 + 0], [2 + 0], [3 + 0],

[0 + 7], [1 + 7], [2 + 7], [3 + 7]이다.

 

각 각의 배열에서 처음 무게부터 최대 무게를 넘지 않는 첫번째 무게까지의 갯수를 세면,

[4][5][6] <= 6  < [7],

[3][4][5][6] <= 6,

[0][1][2][3] <= 6,

6 < [7][8][9][10]

3 + 4 + 4 = 11이다.

 

 

CODE

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long N, C, W[31], ans;
vector<long long> set1;
vector<long long> set2;

void dfs(int s, int e, vector<long long>& v, long long sum)    //&(참조자)는 변수의 담긴 값을 읽는 게 아니라, 그 값의 주소를 읽는 역할을 한다.
{
	if(s > e)    //집합의 처음부터 끝까지 모든 물건에 대해서 선택 유무를 가렸으면 그 경우의 무게를 반환.
	{
		v.push_back(sum);
		return;
	}
	else
	{
		dfs(s+1, e, v, sum);    //선택한다.
		dfs(s+1, e, v, sum+W[s]);    //선택하지 않는다.
	}
}

int main()
{
	cin >> N >> C;
	
	for(int i = 0; i < N; i++)
	{
		cin >> W[i];
	}
	
	//N개의 물건을 비슷한 크기의 집합으로 반으로 나눠서 각 각의 경우 구하기. 
	dfs(0, N/2, set1, 0);
	dfs(N/2 + 1, N-1, set2, 0);
    
    
	sort(set2.begin(), set2.end());    //두 번째 집합에서 구한 모든 경우의 무게를 오름차순 정렬.
    
	for(int i = 0; i < set1.size(); i++)    //첫 번째 집합에서 구한 모든 경우의 무게에 대해서
	{
		ans += upper_bound(set2.begin(), set2.end(), C - set1[i]) - set2.begin(); //s2 + s1 <= C -> s2 <= C - s1
	}
	
	cout << ans << "\n";
}

 

 

 

 

&(참조자)는 변수의 담긴 값을 읽는 게 아니라, 그 값의 주소를 읽는 역할을 한다.