[BOJ] 7453 : 합이 0인 네 정수

7453 : 합이 0인 네 정수

풀이

브루트포스

equal_range를 잘 사용한 예시.

n^4은 너무 크니까 n^2 + n^2개로 쪼갠뒤에

a+b = -(c+d)를 만족하는 것들을 모두 센다.

셀때 원하는값의 로우바운드,어퍼바운드를 계산해주는 equal_range를 사용했고,

equal_range는 페어로 리턴되는데 second-first하면 정답의 개수가 나온다.

정답의 개수를 모두 더하면 답을 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> first, second;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            first.push_back(a[i] + b[j]);
            second.push_back(c[i] + d[j]);
        }
    }
    sort(second.begin(), second.end());
    long long ans = 0;
    for (auto num : first) {
        auto range = equal_range(second.begin(), second.end(), -num);
        ans += range.second - range.first;
    }
    cout << ans;
    return 0;
}

Written on May 14, 2019