[백준] 1208번 : 부분수열의 합2

🤔 문제분석

📝 문제요약

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하시오.

🎯 필요한 개념

• 이분탐색
• 해시맵

✅ 알고리즘

N의 범위가 40이하라서 완전탐색을 할경우 2^40 의 경우의 수를 모두 탐색해야한다. 왼쪽, 오른쪽을 반으로 나누어서 각각 탐색을 수행한다면 주어진 시간안에 문제를 해결 할 수 있다.

해시맵을 사용하여 right, left를 각각 나누어서 자기자신을 포함한경우 포함하지 않은 경우 모두를 탐색한다.

1. 오른쪽을 완전탐색한다.
   1. 종료조건에는 그동안 누적한 cnt에 대해서 경우의 수를 추가한다.
   2. 자기자신을 포함한경우와 포함하지않은경우 두가지에 대해서 탐색한다.
2. 왼쪽을 완전탐색한다.
   1. 종료조건에는 오른쪽에서 갱신한 해시맵을 현재 더한값과 비교하여 정답의 경우의 수에 누적한다.
   2. 자기자신을 포함한경우와 포함하지않은경우 두가지에 대해서 탐색한다.
3. S가 0인경우는 부분수열이 공집한인 경우인 하나를 뺀다.

💻 코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;
// -3, -2, -7, 5, 8
int N, S;
vector<int> arr;
unordered_map<int, int> map;
long long answer = 0;
void right(int mid, int sum)
{
    if(mid == N)
    {
        map[sum] += 1;
        return;
    }

    right(mid + 1, sum);
    right(mid + 1, sum + arr[mid]);
}

void left(int start, int sum)
{
    if(start == N / 2)
    {
        answer += map[S-sum];
        return;
    }

    left(start + 1, sum);
    left(start + 1, sum + arr[start]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> S;
    arr.resize(N, 0);

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

    right(N/2, 0);
    left(0, 0);
    if(S == 0)
    {
        cout << answer - 1;
    }
    else
    {
        cout << answer;
    }
}