7453번_합이 0인 네 정수_BOJ

문제 링크

7453번 합이 0인 네 정수 : https://www.acmicpc.net/problem/7453

문제 설명 및 해결 아이디어

모든 경우를 다 탐색하면 O(n^4)이기 때문에 시간초과가 난다.

그래서 4개의 배열 A, B, C, D중 A와 B의 가능한 모든 합을 저장한 벡터와 C와 D의 가능한 모든 합을 저장한 벡터를 둔다. 두 벡터의 합이 0이 되는 경우의 수를 찾으면 된다.

두 개의 배열에서 가능한 모든 합을 구하는 것이 O(n^2)이므로 이 문제는 O(n^2longn^2)에 해결이 가능하다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long int
 
int n, num;
vector<int> vt[4];
vector<int> vtAB;
vector<int> vtCD;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            scanf("%d", &num);
            vt[j].push_back(num);
        }
    }
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            vtAB.push_back(vt[0][i] + vt[1][j]);
            vtCD.push_back(vt[2][i] + vt[3][j]);
        }
    }
 
    sort(vtAB.begin(), vtAB.end());
    sort(vtCD.begin(), vtCD.end());
 
    ll ans = 0;
    ll res, lo, hi;
 
    for (int i = 0; i < vtAB.size(); ++i) {
        res = vtAB[i];
        lo = lower_bound(vtCD.begin(), vtCD.end(), -res) - vtCD.begin();
        hi = upper_bound(vtCD.begin(), vtCD.end(), -res) - vtCD.begin();
 
        ans += (hi - lo);
    }
    printf("%lld\n", ans);
    return 0;
}