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

이 문제는 상당히 까다로운 문제이니, 

 

" n = 4 , c = 3, v = [1,2,3,4]"

 

라는 값으로 재귀가 어떻게 돌아가는지 코드를 보고 그림으로 한번 표현해보자.

 

part1 / part2로 나뉘어서 진행

 

part1을 예로 들어서 설명하겠다. 

part1에는 현재 [1,2] 라는 무게를 담고 있고 재귀를 도는데 

 "1"의 무게를 가진 놈을 담아?  Yes or No (2가지) 

"2"의 무게를 가진 놈을 담아?  Yes or No (2가지) 

 

위의 경우를 가지치기로 만들어진 sum의 개수는 2X2 = 4 가지 이며, 

part1의 sum값은 [ 0, 2, 1, 3] 이 된다. 

part2의 sum값은 [0, 4, 3, 7] 이 된다. 

 

part2는 오름차순으로 정렬을 시킨다. 

[0, 3, 4, 7]

 

여기서 part1 과 part2 을 비교를 한다. 

part1의 원소값의 개수만큼 반복문을 돌린다.

 

 "가방의 무게 - part1[i]" = 더 담을수 있는 무게

 

더 담을수 있는 무게 이하인 값들을 part2에서 찾아서 그 개수를 더해나가면 원하는 결과값을 도출할 수 있다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll;
vector <ll>  v;
void dfs(int start, int end, vector <ll>& part, ll sum) {
	if (start > end) {
		part.push_back(sum); 
		return ; 
	}
	else {
		dfs(start + 1, end, part, sum); 
		dfs(start + 1, end, part, sum + v[start]); 
	}
}
int main() {
	int n, c; cin >> n >> c;	
	v.resize(n, 0); 
	for (int i = 0; i < n; i++)cin >> v[i];
	vector <ll> part1;
	vector <ll> part2;
	dfs(0, n / 2 - 1, part1, 0); 
	dfs(n / 2, n - 1, part2, 0); 
	sort(part2.begin(), part2.end()); 
	int cnt = 0; 
	for (int i = 0; i < part1.size(); i++) {
		ll x = c - part1[i]; 
		cnt += upper_bound(part2.begin(), part2.end(), x) - part2.begin(); 
	}
	cout << cnt; 
}

1450번: 냅색문제