백준 BOJ 1208 - 부분수열의 합 2

boj 1182 부분수열의 합 에서 범위를 두배로 키운 문제.

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

밋인더 미들 알고리즘을 사용한다.

boj 1182에서와 같이, N이 20일때는 모든 경우에 대해서 브루트포싱할때

전체 연산 횟수가 백만 정도여서 깔끔하게 해결이 가능하지만,

N이 40인 이 문제에서는 전체 연산 횟수도 백만의 제곱이어서 시간초과를 받게 된다.

시간초과를 방지하기 위해 입력으로 들어온 배열 N을 크기가 절반인 두 배열

A와 B로 각각 분리해서,

 

A와 B 각각에 대해서 브루트포싱을 통해서 만들수 있는 모든 합을 구해준 다음,

A에서 더한 수 a와 B에서 만든 수 b를 더해서 S를 만들수 있는지 계산해주면 된다.

 

이때, A에서 고른 하나의 수 a에 여러개의 b가 매칭될 수 있으므로,

b의 갯수를 S-a에 대한 upper_bound에서 lower_bound를 빼서 구해줄 수 있다.

 

이때,

A에서 뽑은 수로만 S를 만들수 있는 경우 B에서는 0을 선택할 것이고(아무것도 고르지 않을 것이고)

정 반대도 성립하므로 굳이 구하는 중간에 정답인지 아닌지를 계산해줄 필요는 없다.

 

입력으로 들어온 S가 0일 경우

A와 B 모두에서 0을 골라서(아무것도 고르지 않아서) 세어지는 횟수 1회는

 

크기가 양수인 부분수열 중에서

조건에 의해서 정답에 포함시키면 안되기 때문에,

정답에서 1을 뺀 수를 출력하도록 작성해주면 된다.

 

추가적으로 N의 크기가 1으로 매우 작은 경우 배열을 A와 B로 분리하는 과정에서

실수가 일어나기 쉬우므로

나는 그냥 깔끔하게 N이 1인 경우에 대한 처리를 따로 해줬다.

 

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

ll arr[50] = {0};
vector<ll> A,B;

ll N,S;
ll ans = 0;

void find(int s, int e, ll sum, int type){
	if(s == e){
		if(type == 1) A.push_back(sum);
		if(type == 2) B.push_back(sum);
		return;
	}
	
	find(s+1, e, sum+arr[s], type);
	find(s+1, e, sum, type);
	return;
}

int main(){
	cin >> N >> S;
	for(int i=0; i<N; i++) cin >> arr[i];
	
	if(N == 1 && arr[0] != S){
		if(arr[0] != S){ cout << 0; return 0; }
		if(arr[0] == S){ cout << 1; return 0; }
	}
	
	find(0,N/2+1,0,1);
	find(N/2+1,N,0,2);
	
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	
	for(int i=0; i<A.size(); i++){
		auto low = lower_bound(B.begin(), B.end(), S-A[i]);
		auto up = upper_bound(B.begin(), B.end(), S-A[i]);
		ans += (ll)(up-low);
	}

	cout << ans - (S==0);
	return 0;
}