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

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

7453번: 합이 0인 네 정수

 

 

[ 문제풀이 ]

 

1. 수들을 입력받아 arr 배열에 저장하고, arr 배열에서 두 수를 뽑아 더한 값을 sum 배열에 저장합니다. 

 

2. sum 배열을 오름차순으로 정렬합니다.

 

3. 이중 for문을 이용하여 i = N - 1부터 0까지, j는 0부터 N까지 탐색하면서 arr[ i ] + arr[ j ]가 sum 배열에 존재하는지 lower_bound를 활용하여 찾아줍니다.

 

4. sum 배열에 존재한다면 upper_bound를 활용하여 같은 수가 있다면 그 개수만큼 ans에 더해줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int arr[4][4000];
vector<int> sum;
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    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++) {
            sum.push_back(arr[0][i] + arr[1][j]);
        }
    }
 
    sort(sum.begin(), sum.end());
 
    ll ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp = arr[2][i] + arr[3][j];
 
            auto it = lower_bound(sum.begin(), sum.end(), -temp);
 
            if (*it == -temp) {
                ans += upper_bound(sum.begin(), sum.end(), -temp) - it;
            }
        }
    }
 
    cout << ans;
}