[G1] 백준 1208번 부분수열의 합 2 C++ 이분 탐색, upper_bound, lower_bound

리뷰

 

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

이분 탐색을 통해 부분 수열의 합이 S인 경우의 수를 구하는 문제

 

 

전역 변수

• N : 수열의 길이를 저장할 변수
• S : 목표 값을 저장할 변수
• lst : 수열 정보를 입력 받을 배열
• L, R : 수열을 반으로 자르고 왼쪽, 오른쪽 부분수열의 합을 저장할 벡터

 

함수

1. getSum

void getSum(int s, int e, ll sum, vector<ll>& sums)

 

부분 수열의 합을 구하기 위한 함수

1. 매개 변수로 현재 지점 s, 마지막 지점 e, 누적 합 sum, 벡터 참조 sums를 전달받는다.
2. 기저 조건으로 s가 e보다 커졌을 경우 sums에 sum을 push해주고 리턴해 준다.
3. 기저 조건에 해당하지 않는다면 현재 값을 sum에 추가 하거나, 추가하지 않는 경우를 재귀를 진행해 준다.

 

문제풀이

1. N, S 값을 입력 받고, N개의 원소를 lst배열에 입력 받아준다.
2. 변수 mid에 N을 2로 나눈 몫을 저장해 준다.
3. getSum함수를 통해 부분수열의 합을 0 ~ mid - 1범위면 L에, mid ~ N - 1 범위는 R에 저장해 준다.
4. 이분 탐색 진행을 위해 sort 함수를 통해 벡터 R을 오름차순으로 정렬해 준다.
5. 정답을 저장할 변수 ans를 0으로 초기화 해주고, 벡터 L을 순회해 준다.
6. 변수 target에 S에서 현재 요소를 뺀 값을 저장해 준다.
7. upper_bound를 통해 벡터 R에서 target보다 큰 첫번째 값의 이터레이터를 upper로 저장해 준다.
8. lower_bound를 통해 벡터 R에서 target이상인 첫번째 값의 이터레이터를 lower로 저장해 준다.
9. ans에 upper - lower를 한 값을 더해 준다.
10. 탐색을 마친 후 S가 0인 경우 아무것도 선택하지 않은 경우를 빼주어야 하므로 ans를 1만큼 감소 시켜준다.
11. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 그냥 수열 전체를 재귀를 돌린다면 2^40으로 시간 초과가 발생하게 된다.
• 수열을 반으로 나누어 2^21으로 두 수열의 부분합을 모두 구해준 후 유효한 값이 있는지 체크해 주었다.
• 해시맵과 트리맵을 사용해 중복값 계산을 해보았는데 그냥 lower, upper_bound를 쓰는게 더 빨랐다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#define ll long long
using namespace std;

int N, S;
int lst[40];
vector<ll> L, R;

void getSum(int s, int e, ll sum, vector<ll>& sums) {
    if (s > e) {
        sums.push_back(sum);
        return;
    }
    getSum(s + 1, e, sum, sums);
    getSum(s + 1, e, sum + lst[s], sums);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) cin >> lst[i];

    int mid = N / 2;
    getSum(0, mid - 1, 0, L);
    getSum(mid, N - 1, 0, R);
    sort(R.begin(), R.end());

    ll ans = 0;
    for (ll left_sum : L) {
        ll target = S - left_sum;
        auto upper = upper_bound(R.begin(), R.end(), target);
        auto lower = lower_bound(R.begin(), R.end(), target);
        ans += upper - lower;
    }
    if (S == 0) ans--;
    cout << ans;
}