[백준] 부분수열의 합 2

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

1208번: 부분수열의 합 2

우선 문제부터 간단하게 요약하면,

 

N개의 정수로 이루어진 수열에서 크기가 양수인 부분수열 중, 수열의 원소를 다 더한게 S가 되는 경우의 수를 구해야 하는 문제입니다.

 

부분수열의 정의는 인터넷을 한번 검색하고 시작하는 것이 좋을 것 같습니다.

 

<Solution>

우선 간단하게 시간복잡도를 생각해보면, 최대 40개의 숫자가 나올 수 있으므로 해당 숫자들을 뽑거나 뽑지 않는 가짓수를 생각해보면 2^40 가지로 대략 100만*100만의 연산수 이상을 가지므로 이런 접근은 불가능 합니다.

 

그래서 수열을 양쪽으로 잘라서 각각에 대해 부분수열의 합을 모두 구해서 map 자료 구조에 저장해 두고, 해당 자료구조를 조회하면서 찾는 방식을 사용하였습니다. 부분수열의 합을 모두 구하는 과정은 dfs를 이용하여 진행하면 됩니다. 

 

주의 해야 하는 점은 S가 0으로 주어지게 되면, 양쪽 절반의 수열에서 하나도 뽑지 않는 경우가 있기 때문에 1을 빼주어야 하는 점을 주의 해야 합니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <map>

using namespace std;

int N, S;
int numArray[50];

long long ans;

map<int, int> lmap;
map<int, int> rmap;
int lsum, rsum;

void dfs_fill_map(int step, int array_size, map<int, int>& whichmap, int& whichsum, int* whicharray){
    // when will it end
    if(step == array_size){
        // add current sum to map
        whichmap[whichsum]++;
        return;
    }

    // 고를때
    whichsum += whicharray[step];
    dfs_fill_map(step+1, array_size, whichmap, whichsum, whicharray);
    whichsum -= whicharray[step];

    // 고르지 않을 때
    dfs_fill_map(step+1, array_size, whichmap, whichsum, whicharray);

    return;

}

int main(){
    cin >> N >> S;

    for(int i = 0; i < N; i++){
        cin >> numArray[i];
    }

    // divide numArray in to half
    int * lnumArray = numArray;
    int * rnumArray = numArray+N/2;

    int lsize = N/2; int rsize = N-N/2;

    // find all candidates from lnumArray
    // 뽑거나 안뽑거나 dfs진행
    dfs_fill_map(0, lsize, lmap, lsum, lnumArray);
    dfs_fill_map(0, rsize, rmap, rsum, rnumArray);
    
    // iterate through lmap keys
    for(map<int,int>::iterator iter = lmap.begin(); iter!=lmap.end(); ++iter){
        // find if rmap hs S-iter->first
        if(rmap.find(S-iter->first) == rmap.end()) continue; // if not found 
        ans += (long long)iter->second * rmap[S-iter->first];

    }
    // S 가 0이면 0개 0개 뽑아서 총 0개 뽑는 경우가 존재 -> 뺴주어야함.
    if(!S) ans -=1;

    cout << ans << endl;
    return 0;

}

ps. 이렇게 공간을 양쪽으로 나누는 방식을 meet in the middle 이라고 한다고 합니다.

 

해킹관련해서도 meet in the middle attack이 있었던 것 같은데 나중에 기회가 되면 posting 해보겠습니다.

https://en.wikipedia.org/wiki/Meet-in-the-middle_attack

Meet-in-the-middle attack - Wikipedia