백준/1208번/부분수열의 합2/골드1

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

문제 설명

Site: Baekjoon
Number: 1208
Category: Meet in the Middle
Rank: Gold 1

주어진 수열에서 부분 수열의 합이 S가 되는 모든 부분 수열의 갯수를 구하는 문제입니다.

문제 풀이

N의 최대치가 40이기 때문에 모든 경우의 수를 확인한다면 2^40만큼의 경우의 수가 나와 시간 초과가 발생하게 됩니다.

이런 경우에 사용하는 알고리즘이 Meet in the Middle이라는 알고리즘입니다.

Meet in the Middle:길이 가 큰 데이터를 반으로 잘라 합쳐 계산하는 방식

수열을 반으로 갈라 계산한다면 시간 복잡도가 2^40에서 2^20 + 2^20이 되어 기존보다 빠른 시간안에 계산할 수 있습니다.

1. 수열을 반으로 나누어 저장합니다.

2. 한 쪽 수열의 모든 부분 수열의 합을 맵에 저장합니다.

3. 다른 한 쪽 수열의 모든 부분 수열의 합을 계산하며 S와 동일하거나 S에서 합을 뺀 값이 맵에 존재한다면 그 값만큼 답의 값을 늘립니다.

4. 마지막으로 한 쪽 수열만의 답을 추가하기 위해 S가 나온 맵의 값과 계산한 답을 더한다면 답이 도출됩니다.

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

using namespace std;

#define PII pair<int, int>

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

    long long N, S, ans = 0;
    cin >> N >> S;

    vector<long long> v1;
    vector<long long> v2;
    unordered_map<long long, long long> m;

    for(int i = 0; i < N; i++)
    {
        long long num;
        cin >> num;

        if (i < N / 2)
            v1.push_back(num);
        else
            v2.push_back(num);
    }

    if(v1.size() == 0)
    {
        if (v2[0] == S)
            cout << 1;
        else
            cout << 0;

        return 0;
    }

    queue<PII> q;

    for(int i = 0; i < v1.size(); i++)
    {
        q.emplace(v1[i], i);
    }

    while(!q.empty())
    {
        int curSum = q.front().first;
        int num = q.front().second;
        q.pop();

        m[curSum]++;

        for(int i = num+1; i < v1.size(); i++)
        {
            q.emplace(curSum + v1[i], i);
        }
    }

    for(int i = 0; i < v2.size(); i++)
    {
        q.emplace(v2[i], i);
    }

    while(!q.empty())
    {
        int curSum = q.front().first;
        int num = q.front().second;
        q.pop();

        if (curSum == S)
            ans++;
        ans += m[S - curSum];

        for(int i = num + 1; i < v2.size(); i++)
        {
            q.emplace(curSum + v2[i], i);
        }
    }

    cout << ans + m[S];

    return 0;
}