BOJ 1208번 부분수열의 합 2

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

github : https://github.com/junho0956/Algorithm/blob/master/1208/1208/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 풀기 전에는 기본적으로 집합의 합의 경우를 구해내는 문제인 

1182번 부분수열의 합 https://junho0956.tistory.com/16을 풀어보시면 좋습니다.

 

부분수열의 합2 문제는 1182번 과는 다르게 범위가 2배 늘어난 문제입니다.

기본적으로 N 이 20이면 백만정도의 범위가 나오는데, N 이 40이 되면 1조가 넘는 계산량이 나오기 때문에

1182번과 같은 방식으로 풀면 시간초과가 날 수 밖에 없습니다.

 

이 문제를 해결하기 위해서는 N이 40인 배열을 반으로 나누는 계산이 필요합니다.

그럼 N이 20인 배열을 2번 계산하면 되기때문에 계산량이 확 줄게되어 문제를 해결할 수 있게 됩니다.

 

반으로 쪼갠 배열들의 이름을 A,B 라고 했을 때

원하는 답인 경우의 수는 3가지 방법으로 접근할 수 있습니다.

1. A의 부분집합의 합 중에서 S를 만들 수 있는 경우

2. B의 부분집합의 합 중에서 S를 만들 수 있는 경우

3. A와 B의 부분집합의 합 중에서 A+B로 S를 만들 수 있는 경우

 

1,2번 방법은 부분집합의 합을 만드는 과정에서 1182번 문제와 같이 경우의 수를 구해주시면 됩니다.

 

3번 방법은 S를 A+B로 만들어야하기때문에

A[i] 로 S를 만들기 위해서는 B에서 S-A[i] 가 존재해야한다는 것을 알 수 있습니다.

이를 이용해서, S-A[i] 를 미리 계산해둔 후에 B의 합의 집합내에서 S-A[i] 를 찾아주시면 됩니다.

 

이분탐색을 이용해서 그 범위를 빠르게 찾아주시면 됩니다.

 

lower_bound => 원하는 키값과 같은 값들의 첫번째 위치 또는 키값이 없을때는 키값보다 첫번째로 큰 위치

(ex : 223335566 에서 lower_bound 3 은 인덱스 2) 

upper_bound => 원하는 키값 기준 처음으로 큰 위치

(ex : 223335566 에서 lower_bound 3,4 은 인덱스 5)

 

S-A[i] 라는 것은 같은 값이 여러개가 존재할 수도 있고, 없을수도 있고, 단 하나만 있을 수도 있습니다.

결국 upper_bound 값 - lower_bound 값을 하게 되면 원하는 S-A[i] 의 값들의 갯수를 알 수 있습니다.

이렇게 3번 방법으로 경우의 수를 구하시면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int arr[40];
int N, S;
long long cnt;
vector<int> a, b;
 
void makeA(int idx, int sum) {
    sum += arr[idx];
    if (idx >= N / 2) return;
    // 만약 S를 만들 수 있다면 cnt++을 해준다
    if (sum == S) cnt++;
 
    a.push_back(sum);
    makeA(idx + 1, sum - arr[idx]);
    makeA(idx + 1, sum);
}
 
void makeB(int idx, int sum) {
    sum += arr[idx];
    if (idx >= N) return;
    // 만약 S를 만들 수 있다면 cnt++을 해준다
    if (sum == S) cnt++;
    
    b.push_back(sum);
    makeB(idx + 1, sum - arr[idx]);
    makeB(idx + 1, sum);
}
 
int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    // 벡터 a,b 에 반으로 나눈 각 배열에 대한 만들 수 있는 모든 부분집합의 합들을 미리 구해놓는다
    makeA(0, 0);
    makeB(N / 2, 0);
 
    // 이분탐색을 이용하기 위해서 미리 정렬을 해둔다
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    // 찾고자하는 값의 갯수를 이분탐색을 이용해서 구한다
    for (int i = 0; i < a.size(); i++) {
        int temp = S - a[i];
        int lower = lower_bound(b.begin(), b.end(), temp) - b.begin();
        int upper = upper_bound(b.begin(), b.end(), temp) - b.begin();
        cnt += upper - lower;
    }
 
    cout << cnt;
 
    return 0;
}