[BOJ] #1208 부분수열의 합 2

시간 제한	메모리 제한	정답 비율
1 초	256 MB	21.446 %

1208번: 부분수열의 합 2

 

문제

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

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

해결

key point, 부분집합을 재귀적으로 찾기엔 N이 너무 크기 때문에 절반으로 나눈다.

• 정수 N개를 홀수, 짝수로 나눠 입력받는다. → seq
• 비트마스크를 활용해 부분집합을 구한다. → sub
• 반드시 정렬한다.
  • 정렬을 해야 부분집합을 두 부분으로 나눈 이유가 없어짐!
• 두 그룹으로 나뉜 부분집합을 투 포인터를 활용해 합이 S가 되는 수를 찾는다.
  • l은 left로 가장 작은 값(sub[0]의 시작점)을 가리키고, r은 right로 가장 큰 값(sub[1]의 끝점)을 가리킨다.
  • *l + *r 의 값이
    • S보다 크면 r을 왼쪽으로 한 칸 당기고(--r)
    • S보다 작으면 l을 오른쪽으로 한 칸 당기고(++l)
    • S와 같으면 l은 *l 보다 최초로 큰 값인 곳(upper_bound)으로 이동하고, r은 *r 보다 최초로 작은 값인 곳(lower_bound - 1)으로 이동한다. → p0.second, p1.first
• 마지막으로 찾는 S가 0이라면, 부분집합을 구했을 당시 공집합(0)을 포함하여 구했기 때문에 공집합을 제외하고 출력한다. → ans--;

 

코드

메모리	시간
13528 KB	292 ms

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
 
int main() {
    int n, s;
    scanf("%d%d", &n, &s);
    vector<int> seq[2], sub[2];
    for (int i = 0, num; i < n; ++i) {
        scanf("%d", &num);
        seq[i % 2].push_back(num);
    }
    for (int i = 0; i < 2; ++i) {
        //비트마스크를 이용하여 모든 부분집합 확인
        for (int j = 0; j < (1 << seq[i].size()); j++) {
            int sum = 0;
            for (int k = 0; k < seq[i].size(); ++k)
                if (j & (1 << k)) sum += seq[i][k];
            sub[i].push_back(sum);
        }
        sort(sub[i].begin(), sub[i].end());
    }
 
    auto l = sub[0].begin(), r = sub[1].end() - 1;
    ll ans = 0;
    while (l != sub[0].end() && r >= sub[1].begin()) {
        if (*l + *r == s) {
            auto p0 = equal_range(sub[0].begin(), sub[0].end(), *l);
            auto p1 = equal_range(sub[1].begin(), sub[1].end(), *r);
            ans += (p0.second - p0.first) * (p1.second - p1.first);
            l = p0.second;
            r = p1.first;
            if (r == sub[1].begin()) break;
            --r;
        }
        else if (*l + *r > s) {
            if (r == sub[1].begin()) break;
            --r;
        }
        else ++l;
    }
    if (s == 0) ans--;
    printf("%lld", ans);
    return 0;
}

다른 풀이(lower_bound, upper_bound)

메모리	시간
13528 KB	324 ms

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
// num과 값이 같은 원소 개수 찾는 함수
ll count(vector<int>& seq, int num) {
    // upper_bound(begin, end, num) -> 구간에서 num보다 큰 수들 중 최솟값
    // lower_bound(begin, end, num) -> 구간에서 num보다 작지 않은 값 중 최솟값
    return upper_bound(seq.begin(), seq.end(), num) - lower_bound(seq.begin(), seq.end(), num);
}
 
int main() {
    int n, s;
    scanf("%d%d", &n, &s);
    vector<int> seq[2], sub[2];
    for (int i = 0, num; i < n; ++i) {
        scanf("%d", &num);
        seq[i % 2].push_back(num);
    }
    for (int i = 0; i < 2; ++i) {
        //비트마스크를 이용하여 모든 부분집합 확인
        for (int j = (1 << seq[i].size()); j > 0; j--) {
            int sum = 0;
            for (int k = 0; k < seq[i].size(); ++k)
                if (j & (1 << k)) sum += seq[i][k];
            sub[i].push_back(sum);
        }
        sort(sub[i].begin(), sub[i].end());
    }
 
    auto l = sub[0].begin(), r = sub[1].end() - 1;
    ll ans = 0;
    while (l != sub[0].end() && r >= sub[1].begin()) {
        if (*l + *r == s) {
            ans += count(sub[0], *l) * count(sub[1], *r);
            l = upper_bound(sub[0].begin(), sub[0].end(), *l);
            r = lower_bound(sub[1].begin(), sub[1].end(), *r);
            if (r == sub[1].begin()) break;
            r--;
        }
        else if (*l + *r > s) {
            if (r == sub[1].begin()) break;
            --r;
        }
        else ++l;
    }
    if(s == 0) ans--;
    printf("%lld", ans);
    return 0;
}

시간초과

• lower_bound, upper_bound를 활용해 문제를 풀었을 때는 시간초과가 나서, 위의 코드 처럼 equal_range 함수를 활용하여 문제를 풀었다.
• 뭐가 문제인지 찾아보기 위해 코드를 변형해가며 제출해봤는데 정답은 count 함수에 있었다.

ll count(vector<int> seq, int num) {
	return upper_bound(seq.begin(), seq.end(), num) - lower_bound(seq.begin(), seq.end(), num);
}

ll count(vector<int>& seq, int num) {
    return upper_bound(seq.begin(), seq.end(), num) - lower_bound(seq.begin(), seq.end(), num);
}

• 두 코드의 차이는 함수 선언문에 있다.
• 'll count(vector<int> seq, int num)'이 아니라 'll count(vector<int>& seq, int num)'라고 작성해야 시간초과가 나지 않고 정답처리가 된다!
• 첫 번째 경우에는 vector<int> seq로 모든 배열의 내용이 복사가 되어 공간과 시간이 배열의 크기만큼 할당, 할애가 되고, 두 번째 경우에는 &연산자를 활용하여 주소값만 전달받아 활용하기 때문에 훨씬 합리적으로 사용할 수 있게 된다.
• 특히나 N이 40이면 그 절반이 20일 때, 부분집합의 크기는 최대 억이 넘어가기 때문에 차이가 더 큰 것 같다.
• 이전까지는 큰 경각심을 갖지 않고 두 가지 모두 번갈아가며 사용했던 터라 이번 문제로 중요성을 알게된 것 같다.