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

일반적인 브루트포스로 풀게 되면 O(2^n)이므로 2^40이고, 이는 시간초과가 발생하기 충분한 시간이다.

meet in the middle 알고리즘을 이용해보자.

MITM은 O(2^n)을 O(2*2^(n/2))로 시간복잡도를 낮추는 알고리즘이다.

시간복잡도를 보면 알 수 있듯이 두 개로 나눠서 검사를 하는 듯한 느낌이 난다.

 

문제로 예를 들면 40개의 원소에 대해 한번에 검사하려면 2^40 경우가 존재한다.

근데 40개를 반씩 나눠서 20개, 20개 따로 검사하면 2^20+2^20이 되고, 이는 대략 2백만의 경우이다.

 

그래 20개씩 나눠서 검사하면 그렇게 되는 것은 알겠는데 왜 그 방법을 사용해도 되는 것일까?

우리는 합이 s가 되는 부분수열을 구해야 한다.

20개의 부분수열의 합을 모두 구해놓으면 나머지 20개의 부분수열의 합들과 조합하여 s가 되는 경우를 찾을 수 있다.

 

그럼 2개가 아니라 여러개로 나눌수록 빠른 것 아니냐!? 하는 생각이 들수도 있는데 (나도 그랬고...) 이는 부분수열의 합들을 조합하는 과정에서 시간이 더욱 많이 든다.

 

어쨋든 2개로 나눠서 구현했는데 입력예제를 넣어보면 2가 나올 것이다.

왜냐하면 각각의 부분수열의 합 집합에는 0이 포함되어 있다. 0은 여러 수들의 조합으로 0이 될 수도 있지만 아예 수를 선택하지 않은 경우에도 0이 된다.

그러니까 아예 수를 선택하지 않은 경우가 양쪽 집합에 하나씩 존재하는 것이다.

 

입력예제처럼 합이 0인 부분수열의 개수를 구하려고하면 수를 선택하지 않은 경우가 포함되는데

문제의 조건에는 부분수열의 크기가 양수여야 한다고 명시되어 있다.

그러므로 합이 0인 부분수열의 개수를 구할 때는 1을 빼주어야 한다.

 

---

정답

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int n, s;
long long answer;
vector<int> seq;
unordered_map<int, int> sum_set;

void left_seq(int cur, int sum){
    if (cur == n / 2){
        sum_set[sum]++;
        return ;
    }

    left_seq(cur + 1, sum + seq[cur]);
    left_seq(cur + 1, sum);
}

void right_seq(int cur, int sum){
    if (cur == n){
        answer += sum_set[s - sum];
        return ;
    }

    right_seq(cur + 1, sum + seq[cur]);
    right_seq(cur + 1, sum);
}

void MITM(){
    left_seq(0, 0);
    right_seq(n / 2, 0);
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        seq.push_back(temp);
    }

    //meet in the middle
    MITM();

    //output
    if (s == 0)
        cout << answer - 1;
    else
        cout << answer;
}