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

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<long long>  vec;
 
void dfs(int start, int end, vector<long long>& part, long long sum) 
{
	if (start > end) 
	{
		part.push_back(sum);
		return;
	}
 
	else 
	{
		dfs(start + 1, end, part, sum);
		dfs(start + 1, end, part, sum + vec[start]);
	}
}
int main() 
{
	int N, C; 
	cin >> N >> C;
 
	vec = vector<long long>(N, 0);
 
	for (int i = 0; i < N; ++i)
	{
		cin >> vec[i];
	}
 
	vector<long long> left;
	vector<long long> right;
 
	dfs(0, N / 2 - 1, left, 0);
	dfs(N / 2, N - 1, right, 0);
 
	sort(right.begin(), right.end());
 
	int count = 0;
 
	for (int i = 0; i < left.size(); ++i)
	{
		count += upper_bound(right.begin(), right.end(), C - left[i]) - right.begin();
	}
 
	cout << count;
 
	return 0;
}

이게 왜 투포인터인가... 싶은 느낌의 문제였는데

모든 수를 넣었다 뺏다 하려니까 2의 30승으로 시간이 모자르더라구요.

최대를 반으로 나눠서 시간을 나눴습니다. 최대를 2의 15승 두번으로 나눴습니다.

이후 갯수를 세주는 upper_bound로 왼쪽과 오른쪽의 합이 C를 넘지 않는 경우를 구해서 count에 더해줍니다.