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

분류: 이분 탐색, 백트래킹 /

 

문제

문제 링크

문제 설명

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

풀이

#include <iostream>
#include <map>
using namespace std;

int N, S;
int num[40];
long long ans;
map<int, int> memo;

void BackTracking(bool isLeft, int cur, int end, int acc) {
    if(cur == end) {
        if(isLeft) memo[S - acc]++;
        else if(memo.count(acc)) ans += memo[acc];
        return;
    }
    BackTracking(isLeft, cur+1, end, acc);
    BackTracking(isLeft, cur+1, end, acc + num[cur]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> S;
    for(int i=0; i<N; i++) cin >> num[i];
    BackTracking(true, 0, N/2, 0);
    BackTracking(false, N/2, N, 0);
    if(S == 0) ans--;
    cout << ans;
}

[백준 - 1182] 부분수열의 합 문제 와 이 문제의 차이는 입력의 크기다.

부분수열의 합 문제는 `N`의 최댓값이 20이고 이 문제의 경우 최댓값이 40이다.

`N ≤ 20`일 경우 최대 전체 경우의 수는 2²⁰(대략 1e6)이므로 백트래킹을 이용해 완전탐색을 해도 시간내에 해를 구할 수 있다.

하지만 `N ≤ 40`일 경우 최대 전체 경우의 수는 2⁴⁰(대략 1e12)이므로 백트래킹을 이용해 완전탐색을 한다면 시간 초과다.

 

절반에 대해서는 해결가능하지만 전체 경우에서 시간초과인 점에서 LeetCode를 풀면 제일 먼저 푸는 two sum 문제를 떠올렸다.

[백준 - 1182] 부분수열의 합 문제의 입력이 정확히 절반이 아니었다면 생각해내기 어려웠을 것 같다.

 

부분수열의 절반에 대한 합을 계산하고 그에 대응되는 수에 카운트를 기록한다. 

나머지 절반의 합을 계산하며 기록된 카운트의 합을 구하면 답이된다.

이때 `S == 0`인 경우 백트래킹에서 공집합에 의해 `memo[0] = 1`은 항상 생기므로 답에서 1을 뺀다.