[백준/Baekjoon] 1208 부분수열의 합 2 C++ :: Binary Search

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

1208번: 부분수열의 합 2

---

1. Logic

완전탐색으로 이 문제를 풀게되면 2^40을 하면 약 1조정도가 나와 당연히 시간초과가 당연히 뜰것같았다. 그래서 시간복잡도가 O(logN)인 이분탐색을 써서 풀면되겠다는 생각을 했다.

 

이분탐색을 input의 반을 나눠서 왼쪽과 오른쪽 부분에 대해 탐색을 돌고

0~n/2까지의 구간의 부분수열의 합을 map에 넣어준다.

n/2~n까지의 구간의 부분수열의 합을 map에 더해주는데 이때 기존에 넣었던 값이 m이랑 같으면 cnt를 하나 올려준다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, s;
vector<int> input;
long long ans;
map<int, int> m;

void left(int idx, int sum) {
    if(idx == n / 2) {
        m[sum]++;
        return;
    }
    left(idx+1, sum);
    left(idx+1, sum + input[idx]);
}

void right(int idx, int sum) {
    if(idx == n) {
        ans += m[s - sum];
        return;
    }
    right(idx+1, sum);
    right(idx+1, sum + input[idx]);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> s;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

    left(0, 0);
    right(n/2, 0);

    if(s == 0) ans--;
    cout << ans;
}

---

3. Feedback

이분탐색으로 푸는 것 까지는 떠올렸지만 어떻게 이분탐색으로 접근할 지는 생각해내지 못해서 여러 블로그들을 참고하며 생각해보았다. 어떻게 이런생각을 하는건지 진짜 궁금하다. 다른 사람의 사고 회로를 뜯어보고싶다,,,, 열심히 해야징~><

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90