백준 1208 : 부분수열의 합 2

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

1208번: 부분수열의 합 2

 

​

부분수열의 합 1에서는 주어진 정수의 개수 N이 20을 넘지 않기 때문에, 2^20안에 해결할 수 있었습니다.

하지만 이번 문제에서는 주어진 정수의 개수 N이 40을 넘지 않기 때문에, 똑같은 방식으로 해결하려고 하면 2^40의 시간이 걸리며 시간초과가 나는 문제였습니다.

마땅히 해결할 방법이 떠오르지 않아 다른 분들의 풀이를 참고하였습니다.

​

주어진 예제 입력으로 해결해보겠습니다.

5 0 -7 -3 -2 5 8

​

1. 먼저 주어진 정수 배열을 두 개로 나눕니다.

배열1 = { -3, -7 };

배열2 = { -2, 5, 8 };

​

2. 두 개로 나뉜 각 정수 배열에 대하여 모든 부분 수열의 합을 각각 구해줍니다.

3. 두 배열을 정렬해줍니다.

부분수열합1(A배열) = { -10, -7, -3, 0 };

부분수열합2(B배열) = { -2, 0, 3, 5, 6, 8, 11, 13};

​

4. 각 배열의 index 변수를 i 와 j 라고 할 때, i는 A 배열의 시작점(0), j는 B 배열의 끝점(B.size() - 1)으로 초기화하겠습니다. A 배열은 가장 작은 값부터, B 배열은 가장 큰 값부터 시작하는 것입니다.

A[i] + B[j] < S 이면, 두 배열의 합(부분 수열의 합)을 늘려야합니다. A 배열의 인덱스 i를 1 증가시켜줍니다.

A[i] + B[j] > S 이면, 두 배열의 합(부분 수열의 합)을 줄여야합니다. B 배열의 인덱스 j를 1 감소시켜줍니다.

A[i] + B[j] == S 이면, S와 일치하는 부분 수열의 합의 개수를 구해야합니다.

이 때, A[i], A[i+1], ... 의 값들이 A[i]와 동일하고, B[j], B[j-1], ... 의 값들이 B[j]와 동일하다면,

(S와 일치하는 부분 수열의 합의 개수 = A[i]와 연속해서 동일한 갯수 * B[j]와 연속해서 동일한 갯수) 입니다.

​

예를 들어,

A = [0, 1, 1, 2]

B = [1, 1, 1, 2] 에서 S == 2, 현재 i = 1, j = 2라고 가정하겠습니다.

A[i] + B[j] == 2 입니다. 부분 수열의 합의 개수를 구해야합니다.

A[i]와 연속해서 동일한 값들은 2개, B[i]와 연속해서 동일한 값들은 3개 입니다.

각 값들에 녹아있는 부분 수열의 합을 조합하여 만들 수 있는 개수는 2*3 = 6개 입니다.

​

부분 수열의 합의 개수를 구했다면, 이동한 i 와 j 값을 가지고 위 과정을 반복해서 수행해줍니다.

​

5. 만약, S == 0 이었다면, A와 B 배열에는 0이 중복해서 들어가있으므로, 합의 개수에서 1을 감소시켜줍니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, s, a[40];
long long int c = 0, c1, c2;
vector<int> l, r;
void f(int idx, int end, int sum, int d) {
    if (idx == end) {
        if (d) l.push_back(sum);
        else r.push_back(sum);
        return;
    }
    f(idx + 1, end, sum, d);
    f(idx + 1, end, sum + a[idx], d);
}
int main() {
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    f(0, n / 2, 0, 1);
    f(n / 2, n, 0, 0);

    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    for (int s1 = 0, s2 = r.size() - 1; s1 < l.size() && s2 >= 0;) {
        if (l[s1] + r[s2] == s) {
            c1 = c2 = 0;
            for (int t = l[s1]; s1 < l.size() && t == l[s1]; s1++, c1++);
            for (int t = r[s2]; s2 >= 0 && t == r[s2]; s2--, c2++);
            c += c1 * c2;
        }
        else if (l[s1] + r[s2] < s) s1++;
        else s2--;
    }
    printf("%lld", s == 0 ? c - 1 : c);
}