[백준/Baekjoon] 3151 합이 0 C++ :: Binary Search

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

3151번: 합이 0

---

1. Logic

두개의 수를 먼저 골라 합을 만들어 놓고 나머지 한개의 수를 골라  0이 되는 수를 카운트 하면 된다.

 

이 문제에서는 중복되는 수가 나올 수도 있기 때문에 원하는 수가 먼저 나오는 index(lower bound) 원하는 수가 나오는 가장 마지막 index(upper bound) 두개를 구해 빼주어 갯수만큼 구해줬다.

 

밑의 코드에서 tempSum에 -를 붙혀준 이유는 우리는 a+b+c=0이 되는 값을 구해야하는데 2중 for문을 돌며 a+b를 이미 구해놓은 상태이다. 여기서 식을 이항해보면 a+b = -c이기 때문에 c를 구하고 음수로 만들어준 -c와 a+b값이 같으면 0이기 때문에 붙혀준 것이다.

---

2. Code

#include <iostream>
#include<algorithm>
#include <vector>

using namespace std;

vector<int> input;
int n;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        
        input.push_back(a);
    }
    
    sort(input.begin(), input.end());
    
    long long cnt = 0;
    
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            long long tempSum = input[i] + input[j];
            
            int lower = lower_bound(input.begin()+j+1, input.end(), -tempSum) - input.begin();
            int upper = upper_bound(input.begin() +j+1, input.end(), -tempSum) - input.begin();;
            cnt += (upper - lower);
        }
    }
        
    cout << cnt;
}

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

728x90