[C/C++] 백준 1450번 - 냅색문제

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

예제 입력 1

2 1
1 1

예제 출력 1

3

 

 

<코드>

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

long long N,C,W[31],ans;
vector<long long> group1;
vector<long long> group2;

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];
	}
	
	// 반으로 나눠서 경우의수 저장  
	dfs(0, N/2, group1, 0);
	dfs(N/2 + 1, N-1, group2, 0);
	sort(group2.begin(), group2.end());
	
	
	for(int i = 0; i < group1.size(); i++)
	{
		ans += upper_bound(group2.begin(), group2.end(), C - group1[i]) - group2.begin();
	}
	
	cout << ans << endl;
}

 

 

풀이 방법

풀이법이 떠오르지 않아 wookje님 풀이를 참고하였습니다. 

 

<기본 아이디어>

물건의 최대 개수가 30개이고 2의 30승의 경우 10억 7천만이므로 시간초과가 발생한다. 따라서 물건을 반으로 나누어 만들 수 있는 조합을 group1, group2 벡터에 각각 저장해놓는다. 그리고 group2 벡터만 정렬을 한 뒤 group1의 i번째 조합에서 group2의 조합을 더했을 때 가방 최대 무게 C를 넘기지 않는 group2의 인덱스를 upper_bound 함수를 통해 이분 탐색으로 찾아내어서 ans변수에 카운트해주었다. 시간복잡도는 O(2^(N/2)log2^(N/2)) = O(N*2^(N/2)) 이다.

 

 

www.acmicpc.net/problem/1450

1450번: 냅색문제