[BOJ] 합이 0인 네 정수_7453 C++ 풀이

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 $($a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

접근 방법

이 문제를 완전탐색으로 접근할 경우 O$($N⁴)시간이 걸리게 된다. 이는 어마어마한 시간이 소요되며 시간초과를 야기한다. 따라서 이분탐색기법을 활용하여 문제를 접근하였다.

배열 C와 D의 각각의 원소들을 NxN 형태로 일일이 더해준 값들을 임의의 배열 v에 저장해두고 v에 저장한 값들과 배열 A 와 B의 원소를 더한값과 비교하여 같을 경우 합이 0이되는 쌍이므로 cnt++ 해주는 형태로 접근하였다.

하지만 이 접근방식의 오류는 A와 B의 원소를 더한값과 일치하는 값이 배열 v에 여러개 존재하는 경우를 배제한 생각이었다는 것이고 이를 보완하여 생각해낸 아이디어가 바로 범위를 구하는 것이었다.

C와 D 배열의 각 원소값들을 더한 값들이 저장된 배열 v를 오름차순으로 정렬하고 A배열의 원소 + B배열의 원소를 한 값과 부호가 다르면서 일치하는 값$($key값) 이 v에 존재한다면 해당 값이 배열의 시작에서 부터 탐색했을때 처음 발견된 index$($A)에서부터 처음 해당값보다 커지는 index$($B)를 구해서 A-B를 해준다면 오름차순으로 정렬되어 있기 때문에 이는 곧 우리가 찾는 key값이 v배열에 총 A-B개 존재한다는 의미이다.

이러한 범위를 구하기 위해서 아래와 같이 lower_boud, upper_bound함수를 사용하였으며

int num = A[i] + B[j];
int low_idx = lower_bound(v.begin(), v.end(), -num) - v.begin(); // num과 같거나 최소로 큰 v의 index구함
int up_idx = upper_bound(v.begin(), v.end(), -num) - v.begin(); // -num이 v배열에 여러개 존재할 가능성이 있으므로 범위를 구해야함

lower_bound 함수가 key값과 같은 값을 찾았다면 범위를 cnt에 더해주었다.

if((num + v[low_idx])==0)
    cnt += (up_idx - low_idx); //범위 만큼의 개수가 존재 

마지막으로 n의 범위는 1 ≤ n ≤ 4000 이기 때문에 변수 cnt의 자료형을 long long으로 선언해 주어야 했지만 int로 선언하여 한참을 찾는 실수를 하였다.

구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    long long cnt=0;
    cin>>n;

    vector<int> A(n,0);
    vector<int> B(n,0);
    vector<int> C(n,0);
    vector<int> D(n,0);
    vector<int> v;

    for(int i=0; i<n; i++) cin>>A[i]>>B[i]>>C[i]>>D[i];

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            v.push_back(C[i]+D[j]);

    sort(v.begin(), v.end());

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            int num = A[i] + B[j];
            int low_idx = lower_bound(v.begin(), v.end(), -num) - v.begin(); // num과 같거나 최소로 큰 v의 index구함
            int up_idx = upper_bound(v.begin(), v.end(), -num) - v.begin(); // -num이 v배열에 여러개 존재할 가능성이 있으므로 범위를 구해야함

            if((num + v[low_idx])==0)
                cnt += (up_idx - low_idx); //범위 만큼의 개수가 존재 
        }

    cout<<cnt;
    return 0;
}

BOJ_합이 0인 네 정수