백준 1208 / C++ / 이분탐색

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

이 문제는 일단 부분수열의 합의 모든 경우의 수를 구하는 방법을 알아야한다

부분수열을 굳이 연속되지 않아도 부분수열이기때문에

각 원소가 참여했는지 안했는지를 파악해야해서 n개의 원소를 파악할때 2^n개의 경우의 수를  검사해야 한다.
해당 문제를 푸는 방법

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

해당 문제를 참고 하면된다

#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;
}

전체 코드는 이렇게 된다 부분적으로 한번 보자
일단 2의 20승은 1048576이기 때문에 1초연산을 약 100000000번이라고 가정하면 오바되지 않지만
현재 우리의 문제는 최대 2의40승이기에 1,099,511,627,776번 연산은 1초를 넘어간다

 

이에 우리는 2의40승에 대하여 2의 20승 2개로 나눠서 연산을 해준다
이에 우리는 우리가 받은 수열을 20개 짜리로 2개로 나눠서한다고 가정한다
그래서 나눈 왼쪽의 모든 부분수열의 합을  map에다가 저장해주고

오른쪽을 연산할때 오른쪽의 부분수열의 합을 연산할때 s-sum이 존재하면 그만큼의 갯수만큼 카운트를 중가시켜주면된다