1208번

1208번 - 부분집합의 합2

굉장히 까다로운 문제였다. 일단 N제한이 40이다 보니, 부분집합의 갯수만 2^40 이므로 시간제한을 피해갈 수 없었다.

그래서 이 문제는 수열을 두개로 나눠서 문제를 풀어야 했다. (7453번과 비슷)

수열을 두개로 나누고 각 수열에서, 부분집합의 합을 모두 구했다. 최대 N이 40이므로 , 반절은 2^20= 백만 정도 되기 때문에

문제를 푸는데 큰 차질이 없었다.

그 다음 합이 s를 만족하도록 두 수열에서 수를 찾으면 된다. 이때 lower_bound 와 upper_bound를 이용했다.

처음에 공집합에 대한 부분때문에 문제를 계속 틀렸다. 부분집합의 합을 구할 때, 공집합을 빼고보니 나중에 다시 갯수를 구할 때 예외처리를 해줘야 

할 사항이 발생했다.

그래서 그냥 공집합을 넣어서 수열 2개를 만들고, 답이 0 일 경우, 전체 공집합 한개를 빼주면 됐다.

###그 외에 항상 생각할 것

N을 2로 나눌 때는 항상 N이 1일 때, 생각이외의 예외사항이 자주 발생한다는 걸 잊지말자.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> sum1;
vector<int> sum2;
bool first;
void makeAll(vector<int> v, int k, int sum, int num)
{
    if (num == 0)
    {
        if (k == v.size())
        {
            sum1.push_back(sum);
            return;
        }
 
        makeAll(v, k + 1, sum + v[k], num);
        makeAll(v, k + 1, sum, num);
    }
 
    if (num == 1)
    {
        if (k == v.size())
        {
            sum2.push_back(sum);
            return;
        }
 
        makeAll(v, k + 1, sum + v[k], num);
        makeAll(v, k + 1, sum, num);
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, s;
    scanf("%d%d", &n, &s);
    vector<int> v1(n / 2);
    vector<int> v2(n - (n / 2));
    for (int i = 0; i < n / 2; i++)
    {
        scanf("%d", &v1[i]);
    }
 
    for (int i = 0; i < n - (n / 2); i++)
    {
        scanf("%d", &v2[i]);
    }
 
    first = true;
    makeAll(v1, 0, 0, 0);
    first = true;
    makeAll(v2, 0, 0, 1);
 
    //공집합을 나타내는 값
    sort(sum1.begin(), sum1.end());
    sort(sum2.begin(), sum2.end());
 
    int i = 0;
    long long ans = 0;
    while (i < sum2.size())
    {
        int A = sum2[i];
        int findNum = s - A;
 
        auto l = lower_bound(sum1.begin(), sum1.end(), findNum);
        auto u = upper_bound(sum1.begin(), sum1.end(), findNum);
 
        ans += u - l;
 
        i++;
    }
 
    if (s == 0)
    {
        ans--;
    }
 
    printf("%lld\n", ans);
 
    return 0;
}