[C++] 중간에서 만나기(Meet In The Middle)

중간에서 만나기(Meet In The Middle)

알고리즘 문제를 풀 때 완전 탐색으로 탐색하는 경우, 탐색의 범위가 커질수록 경우의 수와 연산량이 기하급수적으로 늘어나는 것을 볼 수가 있다. 이때 중간에서 만나기 방식을 사용하면, 시간 복잡도를 제곱근만큼 줄일 수 있다.

 

중간에서 만나기 방식은 앞쪽과 뒤쪽에서 절반씩 접근하여 중간에서 탐색한 결과가 만나게 하는 탐색 기술을 의미한다. 즉, 중간에서 만난 연산의 결과를 합쳐 전체 결과를 뽑아내는 것이다.

 

문제

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

1208번: 부분수열의 합 2

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

int N, S;
int arr[41];

long long answer;
map<int, int> subsum;

void MeetInTheMiddle(int start, int end, int sum)
{
    if (start == end) {
        if (end == N)
            answer += subsum[S - sum]; // 2. 오른쪽 합(=S-왼쪽 합) 개수 구하기
        else
            subsum[sum]++; // 1. 왼쪽 합 개수 구하기
        return;
    }

    MeetInTheMiddle(start + 1, end, sum + arr[start]);
    MeetInTheMiddle(start + 1, end, sum);
}

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

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

    MeetInTheMiddle(0, N / 2, 0);
    MeetInTheMiddle(N / 2, N, 0);

    // 아무것도 뽑지 않았을 때 빼주기
    answer += S == 0 ? -1 : 0;
    cout << answer;
}