[백준 1450] 냅색문제

백준 10456

유형

이분탐색

풀이

보통 냅색문제와는 다르게 dp로 풀 수 없는 범위가 주어져 있다. 최대 무게가 1^10이기 때문에 다른 풀이 방법이 필요했다.

일단 가방에 넣을 수 있는 모든 경우의 수를 구해야하는데 2^30은 너무 큰 숫자가 나온다 그래서 반으로 나누어 각각 경우의 수를 전부 구한 뒤 합이 C보다 작거나 같은지 판단해주면 된다.

입력을 받을 때 n/2씩 나누어서 입력을 받고 가방의 합이 될 수 있는 모든 경우의 수를 재귀적으로 구한다.

그리고 결과값을 오름차순으로 정렬한 뒤 첫번째 배열은 첫 인덱스부터 시작하고 두번째 배열에서는 두 배열 값의 합이 C를 넘지 않는 최대 인덱스를 찾는다.

upper_bound를 이용하면 쉽게 찾을 수 있고 결과 값이 배열의 첫번째 값이 아니면 이전 인덱스까지의 개수를 정답에 더해주는 과정을 반복해준다.

코드

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

int n, c;
int arr[31];

vector<long long> Left;
vector<long long> Right;
vector<int> l;
vector<int> r;

void dfs(int d, long long cnt, bool flag) {
	if (flag && d == l.size()) {
		Left.push_back(cnt);
		return;
	}
	else if (!flag && d == r.size()) {
		Right.push_back(cnt);
		return;
	}

	if (flag) dfs(d + 1, cnt + l[d], flag);
	else dfs(d + 1, cnt + r[d], flag);

	dfs(d + 1, cnt, flag);
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (i < (n / 2)) l.push_back(x);
		else r.push_back(x);
	}

	dfs(0, 0, true);
	dfs(0, 0, false);

	sort(Right.begin(), Right.end());
	sort(Left.begin(), Left.end());

	long long ans = 0;
	for (int i = 0; i < Left.size(); i++) {
		auto iter = upper_bound(Right.begin(), Right.end(), c - Left[i]);
		if (iter != Right.begin()) {
			ans += iter - Right.begin();
		}
	}

	cout << ans;

	return 0;
}