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

1208번: 부분수열의 합 2

이분 탐색

---

1. 문제 해결 아이디어

 

N이 40개 이므로 모든 부분수열을 다 구하려면 2^40번의 연산이 필요하다. -> 1초안에 풀 수 없다.

 

주어진 수열을 절반씩 나누어서 계산해 보자

 

수열의 길이가 40이라고 가정하자.

20번째 수열부터 40번째 수열(이를 right수열이라고 하자)까지의 모든 부분수열의 합을 구해본다. 

이때 시간복잡도는 O(2^20)이므로 시간은 충분하다.

 

right 부분 수열의 합을 sum이라고 하면 right수열을 탐색하면서 sum 값이 몇 번 나왔는지 map 자료구조를 사용해서 저장한다.

(sum 값이 map의 key가 된다)

 

right부분 수열을 통해서 map함수를 채웠다면 0번째 수열부터 19번째 수열까지(left수열이라고 하자)의 모든 부분 수열의 합을 구한다.

수열을 모두 탐색할 때마다 cnt값을 map[S-sum] 만큼 더해준다.

left수열의 부분수열의 합이 sum인 경우에 map[S-sum]이 존재한다면 해당 map값(right 수열에서 구한 값)과 현재 left 수열의 sum을 더하면 S가 된다는 뜻이다.

right, left수열의 부분 합을 구할 때 공집합인 경우도 있기때문에 left, right만 탐색해서 S를 구하는 경우도 자연스럽게 구할 수 있다.

 

하지만 S가 0인 경우에는 left, right 부분수열 모두 공집합인 경우가 하나 존재하기 때문에 구한 cnt값에서 1을 빼준게 정답이 된다.

---

2. 코드

#include <iostream>
#include <map>
using namespace std;
 
int N, S;
int arr[41];
map<int, int> subsum;
long long cnt;
 
void rightSeq(int mid, int sum){
    if(mid == N){
        subsum[sum]++;
        return;
    }
    
    rightSeq(mid+1, sum+arr[mid]);
    rightSeq(mid+1, sum);
}
 
void leftSeq(int st, int sum){
    if(st == N/2){
        cnt += subsum[S-sum];
        return;
    }
    
    leftSeq(st+1, sum+arr[st]);
    leftSeq(st+1, sum);
}
 
int main(){
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    
    rightSeq(N/2, 0);
    leftSeq(0, 0);
    
    if(!S) cout << cnt-1;
    else cout << cnt;
    
    return 0;
}