[Algorithm] Baekjoon 7453번 : 합이 0인 네 정수

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
// 수 최대 2.68억... n 최대 4천...
 
int n;
int arr[4][4001] = { 0 };
long long answer = 0;
 
vector<int> first;
vector<int> second;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    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)
        {
            first.push_back(arr[0][i] + arr[1][j]);
            second.push_back(arr[2][i] + arr[3][j]);
        }
    }
 
    sort(first.begin(), first.end());
    sort(second.begin(), second.end());
 
    for (int i = 0; i < first.size(); ++i)
    {
        int secondLowerIndex = lower_bound(second.begin(), second.end(), -first[i]) - second.begin();
        int secondUpperIndex = upper_bound(second.begin(), second.end(), -first[i]) - second.begin();
 
        int targetCount = secondUpperIndex - secondLowerIndex;
 
        answer += targetCount;
    }
    
    cout << answer;
}
 
 

 

중간에서만나기... 라는 Middle meet 알고리즘을 활용하는 문제다.

예~~전에 관련 문제를 풀었던 적이 있어서 접근을 잘 했는데, 체크를 map으로 했더니 메모리 초과가 났다;;

그래도 map으로 카운팅하는게 더 빨리 알아낼 수 있긴한데 문제조건이 시간제한이 넉넉하다보니 그냥 벡터로 그때그때 lower_bound랑 upper_bound로 개수 알아내는게 이 문제에 있어선 더 싸게 먹히는 것 같다.