[BOJ 7453] 합이 0인 네 정수

4개의 배열을 가지고, 합이 0이 되도록 구성해야 한다.

 

 

 

이 문제를 브루트포스로 풀게 되면, 배열의 크기는 최대 4000이므로,

 

 

 

4000의 4승이 된다. 시간복잡도가 너무 크므로, 분명히 시간초과가 발생한다.

 

 

 

시간초과가 발생하지 않기 위해서는,

 

 

 

두 개의 배열의 합의 모든 값을 vector 자료구조에 넣는다.

 

 

 

자료구조에 넣은 다음에 정렬을 시킨다.

 

 

 

그리고, 남은 두 개의 배열의 합과 vector의 원소를 합쳤을 때, 0이 되는 값을 찾으면 된다.

 

 

 

vector에 값을 넣은 이유는 0이 되는 값을 찾을 때, 이분탐색(logN)을 하기 위해서이다. 

 

 

 

이렇게 하면, 시간 복잡도는 4000 * 4000 * log(4000 * 4000)으로 줄어드므로 시간초과가 발생하지 않는다.

 

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
long long arr[4][4000];
long long answer = 0;
int N;
vector<long long> v;
pair<vector<long long>::iterator,vector<long long>::iterator> bounds;
 
int main() {
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 4; j++){
            cin >> arr[j][i];
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            v.push_back(arr[2][i] + arr[3][j]);
        }
    }
    sort(v.begin(), v.end());
 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            long long val = arr[0][i] + arr[1][j];
            bounds = equal_range(v.begin(), v.end(), -val);
            answer += (bounds.second - bounds.first);
        }
    }
    
    cout << answer << endl;
    return 0;
}