백준 1208, 부분수열의 합 2

개요

문제 링크
골드 1, Bruteforce, Meet in the middle
40개 원소를 포함하는 수열의 부분수열의 합이 S가 되는 경우의 수

---

접근

1. SSP의 Meet in the middle을 쓰는 세 번째 문제, 1182와 이름도 문제도 똑같은데 왜 티어차이가 이렇게 심할까? 브루트포스의 방식의 차이 때문인데, 이 문제는 전형적인 Meet in the middle 문제니까 잘 알아두도록 하자.
2. SSP를 모른다면 위에 링크된 SSP글을 꼭 읽어보자. 이게 무슨 개념인가 하니, 1182는 N개의 스위치를 가지고 포함/미포함을 선택하는 모든 경우를 따지는 문제였다. 이때 시간복잡도는 O(2^N)인데, 2^40은 대략 1000^4니까 시간에서 터진다.
3. 이때 선택이 중복을 허용하지 않으므로 배열을 반으로 나누고 반은 왼쪽에서, 나머지는 오른쪽에서 선택하자는 개념이 meet in the middle이다. 구체적인 방법은 선택/미선택의 재귀문 두 개를 선언하는 것이고, 아래 의사코드의 내용은 두 함수를 하나로 합친 것이다. 구체적인 방법론은 SSP에서 읽어보자.

---

Pseudo code

void dp(int i,int current,int end) {
    if (i==end) {
        if (end==n) ans+=m[sum-current]; // right=sum-left
        else m[current]++; // left
        return;
    }
    dp(i+1,current,end);
    dp(i+1,current+a[i],end);
}

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define N 41
using ld=long long;
ld n,s,a[N],ans;
map <int,ld> m;

void dp(int i,int k,int e) {
    if (i==e) {
        if (e==n) ans+=m[s-k];
        else m[k]++;
        return;
    }
    dp(i+1,k,e);
    dp(i+1,k+a[i],e);
}

int main() {
    cin>>n>>s;
    for (int i=0;i<n;i++)
        cin>>a[i];
    dp(0,0,n/2);
    dp(n/2,0,n);
    if (!s) ans--;
    cout<<ans;
}