BOJ 7453번 합이 0인 네 정수

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

github : https://github.com/junho0956/Algorithm/blob/master/7453/7453/%EC%86%8C%EC%8A%A4.cpp

 

필요한 설명들을 코드와 함께 주석처리하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
typedef long long ll;
vector<int> v;
int arr[4][4001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> arr[j][i];
 
    // N^4 을 한번에 계산하려고 하면 나중에 3중포문+이분탐색을 해야하는데
    // 이는 4000*4000*4000*log4000.. 시간초과가 발생할 수 밖에 없다.
    // N^2 씩 2개로 배열을 반반으로 나눈 후에 가능한 모든 경우의 수를 계산하자
 
    // 1,2번째 배열로 만들 수 있는 모든 경우의 수를 계산
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            v.push_back(arr[0][i] + arr[1][j]);
 
    // 이분탐색을 위해 정렬
    sort(v.begin(), v.end());
 
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = arr[2][i] + arr[3][j];
            // 0을 만들 수 있는 가능한 범위를 lower_bound, upper_bound 를 이용하여 계산
            int lower = lower_bound(v.begin(), v.end(), 0 - sum) - v.begin();
            int upper = upper_bound(v.begin(), v.end(), 0 - sum) - v.begin();
            cnt += upper - lower;
        }
    }
    
    cout << cnt;
    return 0;
}