백준 16132, 그룹 나누기 (Subset)

개요

문제 링크
골드 4, Knapsack, DP
1부터 N까지의 수열의 부분수열의 합이 전체 합의 절반이 되도록 하는 경우의 수

---

접근

1. SSP의 Knapsack을 쓰는 문제, O(2^n)이나 O(2×2^(n/2))가 O(nS)보다 현저히 크기 때문에 Knapsack을 쓰는 게 이득이다. 시간을 비교해보자.

   $O(2^n)$	$O(2\times 2^{n\over 2})$	$O(nS)$
   2^50	2^26	50×(50×51/2)
   1e15	6.7e7	64000

   Meet in the middle로도 풀 수는 있다. 652ms가 나온다. Knapsack의 연산 횟수가 대략 1000분에 1 정도 되니 1ms가 안돼서 Knapsack은 0ms가 나왔다. 둘 다 아래에 추가해두었다.

2. Knapsack, 배낭 문제로 이 문제를 풀어보자. 이 내용은 SSP에 있는 내용과 거의 똑같으니 더 자세한 접근을 보고 싶으면 참조하자.

3. i번째 원소 이전의 원소를 활용하면서 합을 j로 만드는 경우의 수를 dp[i][j]라고 하면, 다음의 관계가 성립한다.

    dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]

   현재 원소를 선택하지 않는 것과 현재 원소를 선택하는 것을 더해준다. 이때 문제에서 a[i]=i이다.

4. 이러면 어차피 2차원 dp에서 두 행만 사용하므로 두개의 행벡터를 서로 복사해가며 문제를 풀어주면 메모리를 아낄 수 있다.

---

Source code

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

using ld=long long;
using vec=vector<ld>;
ld n,S;

int main() {
    cin>>n;
    S=n*(n+1)/2;
    vec b(S,0),c(S,0);
    c[0]=1;
    if (S%2==0)
        for (int i=1;i<=n;i++) {
            b=c;
            for (int j=i;j<=S/2;j++)
                b[j]+=c[j-i];
            c=b;
        }
    cout<<c[S/2]/2;
}

// Meet in the middle 652ms
#include <bits/stdc++.h>
using namespace std;

using ld=long long;
ld n,S,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+i,e);
}

int main() {
    cin>>n;
    S=n*(n+1)/2;
    if (S%2==0) {
        S/=2;
        dp(1,0,n/2);
        dp(n/2,0,n);
    }
    cout<<ans;
}