7453번

7453번 - 합이 0인 네 정수

이 문제는 재귀함수를 통해서 풀면, 100퍼센트 시간초과에 걸린다. 4000^4이기 때문에 ..

어떻게 풀지 몰라서 다른 사람들의 풀이를 참고해서 풀었다.

배열을 합친 후에 이분탐색을 통해서 문제를 해결했다. 

이분탐색 공부를 다시 시작해봐야 할 것 같다.

이번에 새로 알게 된 점

- upper_bound 와 lower_bound . 이거 이용하면 되게 편하게 쓸 것 같다.

- binary_search 라는 이분탐색 함수가 있다는 것도 처음 알았다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
long long n, ans = 0;
vector<int> B1;
vector<int> B2;
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%lld", &n);
    vector<vector<int>> A(4, vector<int>(n));
    
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            scanf("%d", &A[j][i]);
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            B1.push_back(A[0][i] + A[1][j]);
            B2.push_back(A[2][i] + A[3][j]);
        }
    }
 
    sort(B1.begin(), B1.end());
    sort(B2.begin(), B2.end());
 
    for (int i = 0; i < B1.size(); i++)
    {
        int x = B1[i];
        auto a=lower_bound(B2.begin(), B2.end(), -B1[i]);
        auto b = upper_bound(B2.begin(), B2.end(), -B1[i]);
        while (a != b) 
        {
            ans++;
            a++;
        }
    }
 
    printf("%lld\n", ans);
    return 0;
}