[C++][백준 1208] 부분수열의 합 2

[문제]

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

1208번: 부분수열의 합 2

[문제 풀이]

백준 1182번에서 풀었던 풀이에서는 2^20으로 끝날 수 있기에 시간초과가 나지 않지만 해당 문제에서는 2^40의 경우가 나오기 때문에 해당 방식으로는 풀면 시간초과가 걸린다.

그렇기에 오른쪽과 왼쪽으로 우선 나눈 다음에 두가지 경우에서 answer이 될 수 있는 경우를 파악하는 것이 초점이다.

그런데 여기서 두가지 경우에서 answer이 될 경우를 어떻게 구하냐를 파악할 수가 없어서 인터넷에서 답을 보고 힌트를 얻었다.

c++에서 map을 이용해서 key - value값을 이용해서 해당 문제를 풀었다.

우측을 모두 돈 다음에 나온 값을 map[해당값]++ 로 만들어서 우측에서 나올 수 있는 경우를 모두 체크해 둔뒤에

좌측을 돌고 나온 값을 map[s(요구값) - 좌측값] 에 있다면 해당값을 answer에 더하자.

 

여기서 해당값이 answer이 되는 이유는 위에서도 얘기했지만 우측을 모두 돈 경우가 먼저 끝나고 그 값만큼을 map[]에서 올리기 때문에 s에서 좌측에서 나오는 값만큼을 뺀값이 우측에 있다면 정답이 되는 것이고 없다면 기본값인 0이 되기 때문에 상관이 없다.

[코드]

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

//벡터 생성
vector<int> vec(41,0);
//map(key-value)값을 이용해서 해당 문제를 풀도록 하자.
map<int,int> mp;

int n;
long long answer;

//오른쪽 합계
void right_sum(int loc, int total, int s){

    //만약 위치가 최종위치에 도달했다면
    if(loc == n){
        //map에 현재까지 더한 값을 더하자.
        mp[total]++;
        return;
    }

    //위치 loc을 1씩 더하기. total에 현재 숫자를 더하거나 말기
    right_sum(loc + 1, total + vec[loc], s);
    right_sum(loc + 1, total, s);
    return;
}

//왼쪽 합계
void left_sum(int loc, int total, int s){

    if(loc == n / 2){
        //map에 현재 요구하는 값 s에서 total을 뺀값이 있다면 있는만큼 더하자.
        //해당 값이 더했을때 answer이 될 수 있는 이유는
        //위에 있는 right가 먼저 실행이 끝난뒤에 mp[total] 에 나올 수 있는 값의 경우가 저장이 되어 있다.
        //그렇기에 left에서 나올 수 있는 total을 만약 s에서 뺐을때 해당값이 존재한다면
        //answer에 더할수가 있다.
        //만일 없다면 0으로 되어 있을 거기 때문이다.
        answer += mp[s-total];
        return;
    }

    left_sum(loc + 1, total + vec[loc], s);
    left_sum(loc + 1, total, s);
    return;
}

void solve(int s){

    //오른쪽하고 왼쪽으로 나누어서 더하자.
    right_sum(vec.size() / 2, 0,s);
    left_sum(0,0,s);

    //만약 s가 0이라면 1개를 빼자.
    //여기서 1개를 빼는 이유는 0은 왼쪽, 오른쪽 둘다 겹칠 수 있기 때문인걸로 추측.
    if(s == 0){
        cout<<answer - 1<<endl;
    }
    else{
        cout<<answer<<endl;
    }

    return;
}

int main(){
    int s;
    cin>>n>>s;

    vec = vector<int>(n,0);

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

    solve(s);

    return 0;
}