1. 문제 정리
- N개의 정수로 이루어진 수열이 주어진다.
- 크기가 양수인(0보다 큰) 부분 수열 의 합이 S가 되는 경우의 수를 출력한다.
2. 접근
- 경우의 수를 구하기 위한 완전 탐색의 시간 복잡도는 O(2^n)이다
- 위 시간 복잡도에 해당하는 전체 완전탐색의 경우에는 2^40 = 1099511627776으로 약 1조가 나오므로 시간 제한에 걸리게 된다.
- 위를 해결하기 위해 2분할을 하여 dfs를 이용해 경우의 수를 구한다.
3. 풀이
//2022.01.14
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n, s;
long long a[40];
long long ans = 0;
vector<long long> l, r;
void go(int i, int last, long long sum, vector<long long> &x) {
if (i == last) {
x.push_back(sum);
return;
}
go(i + 1, last, sum + a[i], x);
go(i + 1, last, sum, x);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> s;
for(int i = 0; i < n; i++){
cin >> a[i];
}
go(0, n / 2 + 1, 0, l);
go(n / 2 + 1, n, 0, r);
sort(r.begin(), r.end());
for (long long i: l) {
auto low = lower_bound(r.begin(), r.end(), s - i);
auto up = upper_bound(r.begin(), r.end(), s - i);
ans += up - low;
}
if(s==0) ans--;
cout << ans;
}
- vector<long long> l, r : 2분할 한 전체 수열을 각각 left, right의 약자로 선언하였다.
- void go(int i, int last, long long sum, vector<long long> &x) : 부분 수열의 합의 모든 경우의 수를 vector x에 적재한다.
- int main() : go(0, n / 2 + 1, 0 , l), go(n / 2 + 1, n, 0, r) 을 동작하여 left, right 전체수열의 절반씩에서 나올 수 있는 각각의 모든 경우의 수를 vector l과 r에 저장한다. 이후 for loop를 통해 l에 적재된 각각의 값 i에 대하여 합이 s가 될 수 있는(s - i) vector r의 모든 값의 수를 upper bound와 lower bound를 이용해 구한다.
마지막으로 s가 0일 경우 길이가 1 이상인 부분수열을 이용한다 하였으므로 1개의 경우의 수(길이가 0이어서 합이 0인 경우)를 빼준다.
4. 소감
처음에 완전탐색으로 시도를 했다가 시간 초과를 범했다. 시간 복잡도를 분명 계산해서 풀 수 있는 문제였음에도 그러지 못 한게 많이 아쉬웠다. 그리고 연속된 부분 수열로 착각해 two point 알고리즘을 사용하려 했던 것도 문제를 제대로 이해하지 못 했던 점에서의 실책이었다.
여러모로 아쉬운 문제였지만, 덕분에 부족한 점들을 파악할 수 있었고 lower bound와 upper bound의 사용에 대해서도 좀 더 이해할 수 있는 기회가 되었다.
댓글