1208 부분수열의 합 2

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

1208번: 부분수열의 합 2

 

 

부분수열의 합 1 문제에서 사이즈만 다른 문제.

 

부분수열의 합 1 문제에서는 \( 1 <= N <= 20\) 이기 때문에 완전탐색으로 해결한다고 했을 때 가장 최악의 경우 시간복잡도가 \( O(2^{20})\) 이므로 시간안에 해결 할 수 있었다.

 

하지만 이 문제는 가장 최악의 경우 시간복잡도가 \( O(2^{40}) \) 이기 때문에 해결할 수 없다.

 

Meet in the middle 테크닉을 사용해 문제를 해결 할 수 있었다.

meet in the middle 테크닉은 출발점과 도착점에서 동시에 시간복잡도 \( O(2^{N}) \) 짜리 완전탐색을 진행하여 만날때까지 수행한다.

 

출발점에서만 수행했을 때보다 줄어들어 최종 시간복잡도가 \( O(2^{\frac{N}{2}}) \) 가 된다.

 

이 문제에 적용해보면

\( N \) 짜리 수열을 반으로 나누어 왼쪽 수열의 모든 경우의 수를 map에 저장한 뒤, 오른쪽 수열의 모든 경우의 수를 구할 때 S에서 뺀 만큼이 map에 있는지 확인하여 세면 된다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int n, s;
int ans;
 
void dfsL(int pos, int sum, vector<int>& v, map<int, int>& mp)
{
    if(pos == n/2)
    {
        mp[sum]++;
        return;
    }
    dfsL(pos+1, sum, v, mp);
    dfsL(pos+1, sum+v[pos], v, mp);
}
 
void dfsR(int pos, int sum, vector<int>& v, map<int, int>& mp)
{
    if(pos >= n)
    {
        auto it = mp.find(s-sum);
        if(it != mp.end())
            ans += it->second;
        return;
    }
    dfsR(pos+1, sum+v[pos], v, mp);
    dfsR(pos+1, sum, v, mp);
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> s;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++)
        cin >> v[i];
    map<int, int> mp;
 
    dfsL(0, 0, v, mp);
    dfsR(n/2, 0, v, mp);
 
    if(s == 0) ans--;
    cout << ans;
 
    return 0;
}