문제 출처

1. 문제설명

  • 정수로 이루어진 4칸의 배열이 N개 주어진다.
  • 4개를 추첨해서 0이 되는 쌍의 개수를 구하라



2. 알고리즘 설계

  • lower_bound, upper_bound를 통해 문제를 해결할 수 있다.
  • N이 최대 4000이므로 4중 for문으로 일일히 검사하면 $N^4$..
    • 안봐도 시간초과이다.
  • 4개의 정수를 무조건 사용해야 되므로, 2개씩 짝 지어서 합을 계산한다.
  • 각각을 A, B 벡터에 저장한다.
  • 두 수의 합 A, 다른 두 수의 합 B를 이용해 A + B = 0이 되려면
    • A = -B
    • 즉, A와 B가 같은 걸 찾으면 된다.
  • A == B를 만족하는 쌍은 여러 개 있을 수 있다.
    • 그러나 만족하는 쌍의 index부터 끝까지 탐색을 하면 많은 시간이 소모된다.
  • lower_bound, upper_bound를 이용하면 된다.
    • 전자는 키 값 이상의 원소 위치를 반환하고, 후자는 키 값을 초과하는 원소의 위치를 반환한다.
    • upper-lower를 하면 해당 원소의 개수가 된다.



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, arr[4005][4];
long long ans;
vector<int> A, B;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2] >> arr[i][3];
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            A.push_back(arr[i][0] + arr[j][1]);
            B.push_back(arr[i][2] + arr[j][3]);
        }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(int k : A) {
        int upper = upper_bound(B.begin(), B.end(), -k) - B.begin();
        int lower = lower_bound(B.begin(), B.end(), -k) - B.begin();
        ans += upper-lower;
    }

    cout << ans;

    return 0;
}



4. 소감

  • 이전에 풀었던 문제에서 원소의 개수만 추가된 문제였다.
  • 백준을 풀면서 시간 제한이 12초인 문제는 처음이었다. 제일 긴 게 4초였나..?
  • 그래서 괜히 겁먹었는데, 문제는 쉬운 편이었다.