(C++) - 백준(BOJ) 7453번 : 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

이분 탐색으로 해결한 문제였습니다.

 

풀이방법

 1. 입력 받은 후 loop를 돌며 다음을 저장합니다. sums1에는 a[i] + b[j]들, sums2에는 c[i] + d[j]. 이렇게 a + b의 쌍들과 c + d의 쌍들이 저장되었습니다. 이 후 두 배열을 오름차순으로 정렬합니다.

 

 2. 모든 sums1에 대해 sums2로부터 -sums1[i]인 값을 찾아 그 index를 구합니다. 하나는 -sums[i]이상인 index가 처음나오는 곳(lower_bound, 다른 하나는 초과인 index(upper_bound)를 각각 구합니다. 이 둘의 차이가 4개의 배열들의 합이 0인 것들의 개수가 됩니다.

 

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll nums[4001][4], n, ans;
vector <ll> sums1,sums2;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 4; j++) 
            cin >> nums[i][j];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            sums1.push_back(nums[i][0]+nums[j][1]);
            sums2.push_back(nums[i][2]+nums[j][3]);
        }
    }

    sort(sums1.begin(),sums1.end());
    sort(sums2.begin(),sums2.end());


    for(int i = 0; i < sums1.size(); i++){
        int idx = lower_bound(sums2.begin(),sums2.end(),-sums1[i]) - sums2.begin();
        int endIdx = upper_bound(sums2.begin(),sums2.end(),-sums1[i]) - sums2.begin();
        ans += endIdx - idx;
    }

    cout << ans;
}