백준 1208 / 부분집합의 합 2

굉장히 어려운 문제.

부분집합의 합이라 나올 수 있는 경우의 수의 최대가 2^40. 시간초과가 난다.

그러하므로 n을 2로 나눈 후 두 경우로 나누어 해결해야한다.

n을 2로 나눈 후 두 경우로 나누어 해결하는 알고리즘을 Meet in the middle, MITM이라 부른다고 한다.

 

1. n개의 수를 n/2짜리 배열과 n/2짜리 배열 두 개로 나누어 담는다.

2. 각각의 배열에 담긴 수의 부분집합의 합을 모두 구하여 새로운 배열 n1, n2에 담는다.

3. n1의 인덱스 하나 n2의 인덱스 하나를 합한 값을 정답 s와 비교하여 체크한다. (투 포인터스 알고리즘 이용)

여기서 가장 어려웠던 건 투 포인터스 알고리즘을 이용하는 법이다.

          

위의 배열이 n1, 밑의 배열이 n2라 가정하자.

n1은 시작 인덱스부터, n2는 마지막 인덱스부터 시작한다.

화살표에 표시된 값을 더한 값이 s보다 작으면 n1의 체커를 오른쪽으로 이동한다. (값 증가)

화살표에 표시된 값을 더한 값이 s보다 크면 n2의 체커를 왼쪽으로 이동한다. (값 감소)

더한 값이 s와 같으면 

지금 n1의 체커가 가르키고 있는 값과 같은 값들의 개수를 c1, 

n2의 체커가 가르치고 있는 값과 같은 값들의 개수를 c2라 할때

답에 c1*c2를 더한다 (1대1 대응)

만약 s가 0일 떄 구한 정답에 1를 빼준다. 

코드 (94~116줄의 코드가 투포인터스알고리즘 코드)

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int>arr1;
vector<int>arr2;
 
vector<int>make1;
vector<int>make2;
 
vector<int>bubun1;
vector<int>bubun2;
 
void go(int idx, int limit, vector<int>&make, int c) {
    if (idx == limit) {
        if (c == 1) {
            int sum = 0;
            for (int i = 0; i < make.size(); i++) {
                if (make[i] == 1) {
                    sum += arr1[i];
                }
            }
        
            bubun1.push_back(sum);
        }
        if (c == 2) {
            int sum = 0;
 
            for (int i = 0; i < make.size(); i++) {
                if (make[i] == 1) {
                    sum += arr2[i];
                }
            }
            bubun2.push_back(sum);
        }
        return;
    }
 
    make[idx] = 0;
    go(idx + 1, limit, make, c);
    make[idx] = 1;
    go(idx + 1, limit, make, c);
 
}
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int n, s;
 
    cin >> n >> s;
 
    int n1, n2;
    n1 = n / 2;
    n2 = n - n1;
 
    for (int i = 0; i < n1; i++) {
        int tmp;
        cin >> tmp;
        arr1.push_back(tmp);
    }
 
    for (int i = n1; i < n; i++) {
        int tmp;
        cin >> tmp;
        arr2.push_back(tmp);
    }
 
    for (int i = 0; i < n1; i++) {
        make1.push_back(0);
    }
    for (int i = 0; i < n2; i++) {
        make2.push_back(0);
    }
 
    long long ans = 0;
 
    go(0, n1,make1,1);
    go(0, n2, make2,2);
 
    sort(bubun1.begin(), bubun1.end());
    sort(bubun2.begin(), bubun2.end());
    reverse(bubun2.begin(), bubun2.end());
 
    int left = 0;
    int right = 0;
    
    int leftl = bubun1.size();
    int rightl = bubun2.size();
 
    while (left < leftl && right < rightl) {
        if (bubun1[left] + bubun2[right] == s) {
            long long c1 = 1;
            long long c2 = 1;
            left++;
            right++;
            while (left < leftl && bubun1[left] == bubun1[left - 1]) {
                c1++;
                left++;
            }
            while (right < rightl && bubun2[right] == bubun2[right - 1]) {
                c2++;
                right++;
            }
            ans += c1 * c2;
        }
        else if (bubun1[left] + bubun2[right] < s) {
            left++;
        }
        else if (bubun1[left] + bubun2[right] > s) {
            right++;
        }
    }
    if (s == 0)ans--;
    cout << ans;
 
}

(p.s 시간초과를 해결해야하는 문제가 가장 어려운 것 같다.)