[BOJ] 합이 0인 네 정수

문제

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

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

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

 

7453

맞았습니다!!

165956

1292

C++14 / 수정

1049

 

1) 비슷한 유형의 문제 

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

2143번: 두 배열의 합

풀이

2020/02/10 - [BOJ/C++] - [BOJ] 두 배열의 합

[BOJ] 두 배열의 합

 

2) 완탐을 이용했다.

n의 크기가 4000인데 4000짜리 배열이 4개 있으므로 O(160000...)으로 네 배열을 한 번에 접근하려고 하면 안된다. 

그래서 A, B/  C, D 배열에서 나올 수 있는 모든 조합을 구한 후, T에서 뺀 값이 C, D 조합에 있는 구간을 구했다. 

 

3) 탐색 시간을 줄이기 위해 이분 탐색을 이용해서 

int target = T - (A, C 조합 중 한 값)

upper_bound(C,D의 조합에서 target보다 큰 값의 인덱스를 가져온다.)

lower_bound(C,D의 조합에서 target이상인 값의 인덱스를 가져온다.)

 

여기서 0이 되는 쌍의 개수는 upper - lower의 개수이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAXX 4001
using namespace std;
 
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    int a[MAXX] = {0}, b[MAXX] = {0}, c[MAXX] = {0}, d[MAXX] = {0};
 
    vector<int> resL, resR;
 
    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++) 
        {
            resL.push_back(a[i] + b[j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) 
        {
            resR.push_back(c[i] + d[j]);
        }
    }
 
    sort(resR.begin(), resR.end());
 
    ll ans = 0;
    for (int i = 0; i < resL.size(); i++) {
        int diff = 0 - resL[i];
 
        vector<int> :: iterator up = upper_bound(resR.begin(), resR.end(), diff);
        vector<int> :: iterator lo = lower_bound(resR.begin(), resR.end(), diff);
        
        ans += up-lo;
    }
    cout << ans << '\n';
    return 0;
}