[BOJ] 1208번 - 부분수열의 합 2

백준 1208번 - 부분수열의 합 2

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	11577	2600	1637	21.967%

문제

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

입력

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

출력

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

---

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

출처

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

알고리즘 분류

• 이분 탐색
• meet in the middle

접근 방법

N의 범위가 40까지이므로, 일반적인 완전탐색으로는 원하는 해를 시간 제한 내에 풀 수 없다.

하지만 N이 20이 될 때는 시도해볼만한 시간이다. 이렇게 N의 범위의 절반 값으로 문제를 해결 할 수 있을 때, Meet in the middle 기법을 고려해볼 수 있다.

Meet in the middle 의 핵심 원리는 절반 크기의 비슷한 문제를 두 번 해결한 결과를 통해 시간복잡도의 개선을 꾀하는 방법이라는 것이다.

즉, ${2^n  > 2^{n/2} + 2^{n/2} }$ 라는 사실을 활용하여 문제를 해결하는 것이다.

 

그러면, 전체 문제를 비슷한 문제 2개로 쪼개는 작업을 시작해보자.

원래의 전체 문제는 "모든 부분수열 중 합이 S가 되는 부분 수열의 개수" 이다.

이제, mid 값을 기준으로 [0~mid), [mid, N) 로 두 개의 문제로 쪼개보자. 우리가 찾고자 하는 합이 S가 되는 부분수열은 3가지 case 에 속한다. 

 

1. 부분 수열이 [0~mid) 에만 속한다.

2. 부분 수열이 [mid~N) 에만 속한다.

3. 부분 수열이 left, right에 걸쳐 존재한다.

 

가장 까다로운 조건인 3번 case 부터 고려 해보자.

meet in the middle 기법을 적용하자면, left에서 모든 합이 K가 되는 수열들의 개수를 완전 탐색으로 cnt라는 맵에 카운팅 해주고 right 에서 완전 탐색을 통해서 나올 수 있는 모든 합(sum)이 sum + K = S 가 되는 K가 left에서 카운팅이 되었다면 그 개수만큼 부분 수열들이 생길 수 있으므로, 그 만큼 정답에 더해준다.

 

이제 1번 case를 고려해보자.

이미 left_dfs를 수행하였을 때, cnt[S]에 카운팅이 되어있을 것이다. 따로, right_dfs했을 때 오른쪽에서 공집합을 선택하는 경우에 이 case 또한 모두 커버되므로 3번 case에 포함된다.

 

마지막으로 2번 case를 고려해보자.

right_dfs를 수행할 때, right에서 만들어진 모든 합(sum)이 S가 되는 경우가 이에 속한다.

이러한 경우가 생길 경우, 정답에 하나씩 추가해주는 식으로 구현하였다.

 

이렇게 구현을 하는 경우, left, right 가 모두 공집합이 되는 1가지 경우가 cnt라는 맵에 포함되게 된다.

즉, 이 경우는 우리가 찾고자 하는 부분수열에 포함되는 것이 아니며 우리가 찾고자하는 S가 0일 경우에 이러한 예외case를 고려하여 -1 한 값을 출력한다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, S;
vector<int> arr;
map<int, int> cnt ;
long long ans = 0 ;
void left_dfs(int sum, int current, int end){
    if( current == end ){
        cnt[sum] += 1;
        return ;
    }
    left_dfs(sum, current+1, end);
    left_dfs(sum + arr[current], current+1, end);
}
void right_dfs(int sum, int current, int end){
    if( current == end ){
        // cnt[K-sum] > 0 일 때, left_subarray에서 선택했을 때 값이 존재
        if( cnt[S-sum] > 0 )
            ans += cnt[S-sum];
        // right 에서만 선택할 때
        else if( sum == S )
            ans += 1;
        return ;
    }
    right_dfs(sum, current+1, end);
    right_dfs(sum + arr[current], current+1, end);
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> S;
    arr.resize(N);

    for(int i=0; i<N; i++)
        cin >> arr[i];

    int m = N/2;
    left_dfs(0, 0, m);
    right_dfs(0, m, N);

    // 공집합을 선택할 경우도 하나 포함됨.
    if( S == 0 ) ans -= 1;
    cout << ans ;

    return 0;
}