백준 1208 부분수열의 합 2 C++

 

간단한 해설

 

meet in middle을 활용하면 된다.

 

중간에서 만나기를 활용하지 않을 경우, n이 최대 40이라서 부분 수열의 개수가 2^40의 경우가 나오게 된다.

 

그러나, 중간에서 만나기를 활용하는 경우 왼쪽 부분 수열 2^20, 오른쪽 부분 수열 2^20, 총 부분 수열의 개수는 2*2^20=2^21이다.

 

왼쪽 부분 수열 합 배열을 만들고, 그 배열에서 값을 선택하고 오른쪽 부분 수열에서 (S - 값)을 구하면 된다.

물론 왼쪽에서만 S가 나올 수 있고, 오른쪽에서만 S가 나올 수 있다.

 

반례는 다음과 같다.

 

4 1
0 0 0 1

answer: 8

4 0
0 0 0 0

answer: 15

40 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

answer: 1099511627775

 

참고로 답이 최대 2^40-1까지 나올 수 있어서 long long 형으로 해야한다.

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
vector<ll> v;
vector<ll> leftV;
vector<ll> rightV;
vector<ll> leftPartialSum;
vector<ll> rightPartialSum;
vector<bool> visited;
vector<ll> picker;
ll n,s,mid;
void leftPick(int topick){
	if(topick==0){
		ll tmpSum=0;
		for(int i=0;i<picker.size();++i){
			tmpSum+=leftV[picker[i]];
		}
		leftPartialSum.push_back(tmpSum);
		return;
	}
	int idx=picker.empty()?0:picker.back()+1;
	for(int i=idx;i<leftV.size();++i){
		picker.push_back(i);
		leftPick(topick-1);
		picker.pop_back();
	}
}
void rightPick(int topick){
	if(topick==0){
		ll tmpSum=0;
		for(int i=0;i<picker.size();++i){
			tmpSum+=rightV[picker[i]];
		}
		rightPartialSum.push_back(tmpSum);
		return;
	}
	int idx=picker.empty()?0:picker.back()+1;
	for(int i=idx;i<rightV.size();++i){
		picker.push_back(i);
		rightPick(topick-1);
		picker.pop_back();
	}
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n>>s;
	mid=n/2;
	v.resize(n);
	visited.resize(n,false);
	for(int i=0;i<n;++i){
		cin>>v[i];
	}
	sort(v.begin(),v.end());
	for(int i=0;i<mid;++i){
		leftV.push_back(v[i]);
	}
	for(int i=mid;i<n;++i){
		rightV.push_back(v[i]);
	}
	for(int i=leftV.size();i>0;--i){
		leftPick(i);
	}
	for(int i=rightV.size();i>0;--i){
		rightPick(i);
	}
	sort(rightPartialSum.begin(),rightPartialSum.end());
	ll ans=0;
	for(int i=0;i<leftPartialSum.size();++i){
		ll crnVal=leftPartialSum[i];
		ll target=s-crnVal;
		int leftIdx=lower_bound(rightPartialSum.begin(),rightPartialSum.end(),target)-rightPartialSum.begin();
		int rightIdx=upper_bound(rightPartialSum.begin(),rightPartialSum.end(),target)-rightPartialSum.begin();
		ans+=(rightIdx-leftIdx);
	}
	for(auto it=leftPartialSum.begin();it!=leftPartialSum.end();++it){
		ll val=*it;
		if(val==s) ++ans;
	}
	for(auto it=rightPartialSum.begin();it!=rightPartialSum.end();++it){
		ll val=*it;
		if(val==s) ++ans;
	}
	cout<<ans;
}