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

05 Jul 2022 in Develop / Solving

c++

문제 분석

• N개의 정수 중 일부를 합쳐서 목표하는 수 S를 만들어라.

입력조건

숫자의 갯수 N 목표 수 S

풀이과정

• 중간에서 만나기를 활용하였다.
• 주어진 배열을 반으로 쪼갠 후 반끼리의 부분집합을 구하고,
• 한 쪽의 부분집합을 선화하면서, 다른 쪽에서 이분탐색으로 결과값을 구할 수 있는 값의 수를 찾아온다.
• 추가로, 한쪽 부분집합에서만 답이 나오는 경우도 있으므로, 두 부분집합을 선화하며 원소가 답이 되는지를 판단해본다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int nums[40];

vector<int> set1;
vector<int> set2;

void makeset(int sum, int idx, int limit, vector<int> &set) {
    if(idx >= limit) return;
    // 부분집합 만드는 코드.
    // 나를 선택하지 않은 다음 함수 호출.
    makeset(sum, idx+1, limit, set);

    // 나를 선택하고, 그 값을 set에 넣음.
    sum += nums[idx];
    set.push_back(sum);
    makeset(sum, idx+1, limit, set);
    // 나를 선택한 다음 함수 실행.
}

int lowerbound(int target) {
    int st = 0;
    int ed = set2.size();
    while(st < ed) {
        int md = (st + ed)/2;

        if(set2[md] < target) st = md+1;
        else ed = md;
    }
    return st;
}

int upperbound( int target) {
    int st = 0;
    int ed = set2.size();
    while(st < ed) {
        int md = (st + ed)/2;

        if(set2[md] <= target) st = md+1;
        else ed = md;
    }
    return ed;
}

// 중간에서 만나기 활용.
int main() {
    int target;
    cin >> n >> target;

    for(int i = 0; i < n; i++)
        cin >> nums[i];
    // 입력 끝.

    makeset(0, 0, n/2, set1);
    makeset(0, n/2, n, set2);

    // sort(set1.begin(), set1.end());
    sort(set2.begin(), set2.end());

    long long ans = 0;
    for(int num : set1) {
        int low = lowerbound(target - num);
        int upp = upperbound(target - num);
        ans += upp - low;
    }

    // 한쪽 부분집합에서만 답이 생기는 경우도 생각.
    for(int num : set1) if(num == target) ans++;
    for(int num : set2) if(num == target) ans++;
    
    cout << ans << endl;
}