BOJ 1208 - 부분수열의 합 2

• 수열 A[N](1<=N<=40, A[i]는 정수)에 대해 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S(|S|<=1000000)가 되는 경우의 수를 찾는 문제이다.

문제 풀이

• 최대 40개의 원소에 대해 brute-force를 돌리면 O(2^40) (약 10^12)으로 시간초과가 난다. 수열을 반으로 나누어서 2^20을 두 번 탐색한 다음에 각 수열에서 나올 수 있는 원소들의 합 S1, S1로 S를 만드는 경우의 수를 계산하면 된다.

• 탐색하는 과정은 약 10^6(K)이기 때문에 합치는 과정이 전체 시간복잡도를 지배하게 된다. 처음에 이 과정을 upper_bound, lower_bound를 사용해서 logK가 붙어있었다. 정답자들의 코드를 보고 O(K)로 줄였다. 수를 다 합해도 최대 4*10^6이기 때문에 아예 저 크기의 배열로 만들어 저장해도 되는 것을 이용한 것이다.

소스코드

// #include<bits/stdc++.h>
// #define F first
// #define S second
// using namespace std;
// typedef vector<int> vi;

// int n, s, aidx, bidx, ar[40];
// long long int cnt;
// vi a, b, ra, rb;

// void f(vi& cv, vi& sv, int ci, int cs){
// 	if(ci==cv.size()){
// 		sv.push_back(cs);
// 		return;
// 	}
// 	f(cv, sv, ci+1, cs+cv[ci]);
// 	f(cv, sv, ci+1, cs);
// }

// int main()
// {
// 	cin>>n>>s;
// 	for(int i=0;i<n;i++) cin>>ar[i];
// 	for(int i=0;i<n/2;i++) a.push_back(ar[i]);
// 	for(int i=n/2;i<n;i++) b.push_back(ar[i]);
// 	f(a, ra, 0, 0);
// 	f(b, rb, 0, 0);
// 	sort(rb.begin(), rb.end());
// 	for(int i=0;i<ra.size();i++){
// 		vi::iterator iter=lower_bound(rb.begin(), rb.end(), s-ra[i]);
// 		int sz=upper_bound(rb.begin(), rb.end(), s-ra[i])-iter;
// 		if(iter==rb.end()) continue;
// 		if(*iter==s-ra[i]) cnt+=sz;
// 	}
// 	cout<<cnt-(s==0);
// }

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

int n, s, ar[40], ps[4000001];
long long cnt;

void f(int ci, int cs, bool chose){
	if(ci==n/2){
		if(chose==0) return;
		if(s==cs) cnt++;
		ps[cs+2000000]++;
		return;
	}
	f(ci+1, cs+ar[ci], 1);
	f(ci+1, cs, chose);
}
void g(int ci, int cs, bool chose){
	if(ci==n){
		if(chose==0) return;
		if(s==cs) cnt++;
		if(s-cs>2000000 || s-cs<-2000000) return;
		cnt+=ps[s-cs+2000000];
		return;
	}
	g(ci+1, cs+ar[ci], 1);
	g(ci+1, cs, chose);
}

int main()
{
	cin>>n>>s;
	for(int i=0;i<n;i++) cin>>ar[i];

	f(0, 0, 0);
	g(n/2, 0, 0);
	cout<<cnt;
}

풀고나서

• logK를 없애니까 시간복잡도가 logK만큼 줄어들었다.

• Meet in the middle이라는 알고리즘을 사용하는 문제를 처음 풀어본 것 같다. 합이 0인 네 정수도 Meet in the middle을 사용하긴 하지만 이를 모르고 풀었을 때였다. 이 알고리즘은 경우의 수가 너무 많아 해를 탐색할 수 없을 때 사용한다. 원래 문제를 반으로 나눠 경우의 수를 제곱근만큼 줄이는 것이다. 그리고 나온 두 부분의 결과들을 합쳐 원래 문제의 해를 찾아내는데, 이 합치는 과정이 중요한 것 같다. 합치는 데이터를 어떻게 이용하냐, 자료구조를 뭘 쓰느냐에 따라서 코드의 시간복잡도가 결정되기 때문이다. 사용하는 사람에 따라서 효율성이 달라질 수 있기 때문에 이때까지 내가 알던 알고리즘이랑은 다르게 느껴진다. 알고리즘이라기보다는 테크닉(dp같은?)이라고 느껴진다. 근데 또 greedy도 greedy 알고리즘이라고 불리는 거 보면 알맞은 호칭인 것 같기도 하다.