1208 - 부분집합의 합 2

문제 링크

---

 

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

 

 

문제 요약

---

 

크기 \(N\)인 집합이 주어진다. 이 때 부분집합의 합이 \(S\)가 되는 경우의 수를 구하는 문제다.

 

 

문제 풀이

 

 

 

 

---

 

\(N\)이 최대 40이기 때문에 완전탐색으로는 안된다. 따라서 다른 방법이 필요하다. 이런 경우에는 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 각각 구하고 이분탐색을 통해 이 경우의 수를 합쳐나갈 수 있다.

 

크기 \(N\)인 집합을 왼쪽부터 \(N \above 1pt 2\)개의 완전탐색 경우의 나머지 오른쪽의 완전탐색 경우를 다 구해 놓는다. 이 때 왼쪽의 경우의 수와 오른쪽 경우의 수를 어떻게 합쳐야 할까? 왼쪽의 경우 중 가능한 한가지 합이 \(x\)라고 가정을 해 보자. 그렇다면 오른쪽 경우의 수에서 찾아야 할 합은 \(S-x\)가 될 것이다. 따라서 왼쪽의 경우의 수에 대해서 가능한 오른쪽의 모든 경우의 수를 찾아 답에 누적해 나가면 된다.

 

\(N\)이 40일 때 시간복잡도는 \(O(2^{20}log2^{20})\)이므로 시간내에 들어올 수 있다.

 

 

소스 코드

 

 

 

 

---

 

 

#include <stdio.h> #include <vector> #include <algorithm>  using namespace std;  int N, S, A[41];  void func(int pos, int end, int sum, vector<int>& vi) {   if (pos == end) {     vi.push_back(sum);     return;   }   func(pos + 1, end, sum, vi);   func(pos + 1, end, sum + A[pos], vi); }  int main() {   scanf("%d%d", &N, &S);   for (int i = 0 ; i < N ; ++i) {     scanf("%d", &A[i]);   }   vector<int> L, R;   func(0, N / 2, 0, L);   func(N / 2, N, 0, R);      sort(R.begin(), R.end());   long long ans = 0;   for (int val : L) {     int target = S - val;     auto hi = upper_bound(R.begin(), R.end(), target);     auto lo = lower_bound(R.begin(), R.end(), target);     ans += hi - lo;   }      if (S == 0) {     --ans;   }   printf("%lld\n", ans); }