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

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

1208번: 부분수열의 합 2

 

 

[ 문제풀이 ]

 

N개의 정수의 모든 부분 수열을 구하기 위해서는 O(2^N)의 시간이 걸립니다.

 

이 문제에서 N은 40개이므로 총 2^40의 시간이 필요한데 1초는 매우 부족한 시간이므로 N을 반으로 나누어 2^20 * 2 = 2^21의 시간이 걸리도록 했습니다.

 

먼저 왼쪽의 부분 수열의 합을 모두 구해 map에 넣고, 오른쪽 부분 수열의 합을 S의 값과 비교하여 cnt에 map[S-sum]을 더해주었습니다.

 

[ 소스 코드 ]

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int N, S;
int arr[41];
unordered_map<int, int> map;
int sum = 0;
long long cnt = 0;
 
void leftDFS(int level)                //왼쪽 반의 모든 조합을 map에 저장
{
    if (level == N / 2) {
        map[sum]++;
        return;
    }
 
    sum += arr[level];
    leftDFS(level + 1);
    sum -= arr[level];
    leftDFS(level + 1);
}
 
void rightDFS(int level)            //오른쪽 반의 모든 조합을 S와 비교해
{                                    //cnt에 더해줌
    if (level == N) {
        cnt += map[S - sum];
        return;
    }
 
    sum += arr[level];
    rightDFS(level + 1);
    sum -= arr[level];
    rightDFS(level + 1);
}
 
int main()
{
    cin >> N >> S;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    leftDFS(0);
    rightDFS(N / 2);
 
    if (S == 0) cnt--;                //S가 0인 경우 공집합이 2번 들어가므로 1을 빼준다.
 
    cout << cnt;
}