[백준] [C++] 1208번 부분수열의 합2 (조합, 중간에서 만나기)

1. 문제

 

1208번: 부분수열의 합 2 (acmicpc.net)

1208번: 부분수열의 합 2

 

2. 풀이1

 

이 문제는 입력의 크기 때문에 메모이제이션과 완전탐색으로는 해결하지 못한다.

 

따라서 주어진 수열을 절반으로 쪼개

 

각각의 모든 조합의 합을 구한뒤

 

두개의 합이 S인 조합의 개수를 구해야한다.

 

각각 따로 조합의 합을 map의 key로, value에 가짓수를 담고

 

마지막에 right[ s - left[]] 와 left[] 를 곱하면

 

합이 s인 전체의 경우의 수를 구할 수 있다.

 

단 s == 0 일 경우 1을 빼줘야한다. 해당 map에는 공집합인 경우도 포함되어있기때문에  left와 right 둘다 공집합인 경우 부분 수열로 보지 않기 때문이다.

long long 타입으로 계산을 해줘야 오버플로우가 발생하지 않는다. 유의해야한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
int N, S;
vector<int> s;
 
void combination(int lo, int hi, int sum, map<int, int>& cache) {
    if(lo == hi) {
        cache[sum]++;
        return;
    }
   combination(lo+1, hi, sum, cache);
   combination(lo+1, hi, sum+s[lo], cache);
}
 
int main() {
    long long answer = 0;
    cin>>N>>S;
    s = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin>>s[i];
    }
    map<int, int> left;
    map<int, int> right;
    combination(0, N/2, 0, left);
    combination(N/2, N, 0, right);
    for(auto it = left.begin(); it != left.end(); it++) {
        answer += (long long)right[S - it->first]*(long long)it->second;
    }
    if(S == 0) {
        answer--;
    }
    cout<<answer;
}

단 이러한 방식은 운에따르는것같다. right를 계산할때 answer를 같이 계산하면 더 빠르게 계산될 것이다.

보다 빠른 풀이는 right에서 answer를 계산하는것이다.

풀이는 다음과 같다.

백준1208 부분수열의 합2 | JusticeHui가 PS하는 블로그

 

3. 풀이2

절반으로 나눠 비트마스크를 사용하는 문제

2^20 인경우 메모리가 충분해 모든 경우의 수를 비트마스크하여 집어넣을 수 있다.

풀이는 다음과 같다

백준 1208번 부분집합의 합 2 (tistory.com)