BOJ 1450 냅색문제

개요

BOJ 1450 냅색문제

• 백준 온라인 저지 1450번 문제
• BOJ 33단계

C++

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

int N, C;
int A[30];
vector<int> L, R;

void dfs(vector<int>& v, int start, int end, int sum) {
    if(sum > C) return;
	if(start > end) {
		v.push_back(sum);
		return;
	}
	dfs(v, start+1, end, sum);
	dfs(v, start+1, end, sum+A[start]);
}

int solve() {
    dfs(L, 0, N/2-1, 0);
    sort(L.begin(), L.end());
	dfs(R, N/2, N-1, 0);
	sort(R.begin(), R.end());
    int ans = 0;
    int j = R.size()-1;
    for (int i=0; i<L.size(); i++) {
		while(j>=0 && L[i] + R[j] > C) {
		    j--;
		}
		ans += j+1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	cout << solve();
}