[7453번] 합이 0인 네 정수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. lower_bound

2. 정렬

3. 아이디어

이 문제는 합이 0인 네 정수를 찾기위해 가장 Naive한 방법으로는 4중 포문을 방법이 있다.

하지만 이 방법을 이용한다면 TLE를 받게 될 것이고, 따라서 우리는 다음과 같이 생각해본다.

1열  2열  3열  4열

1　　2　　3　　4
5　　5　　9　　2
2　　3　　3　　1

.　　.　　.　　.

.　　.　　.　　.

이런식으로 존재할 때

1,2열의 모든 합과 / 3,4열의 모든 합으로 나눠보자.

이렇게 한다면 N^2 + N^2으로 우선 시간을 줄일 수 있다.

그 후 1,2열의 합을 나타내는 a가 3,4열의 합을 나타내는 b가 있을 때

a - b가 0인지 확인하면 정답을 구할 수 있게 된다.

lower_bound를 이용하여 -a의 첫번째 범위와 upper_bound를 이용하여 -a의 마지막 범위를 찾아낸다면 우리는 답을 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   using namespace std;   typedef long long ll;   ll arr[4][4002];   vector<ll> vc2;   int main() {     int n;     scanf("%d", &n);       for (int j = 0; j < n; j++)         for (int i = 0; i < 4; i++)             scanf("%lld", &arr[i][j]);       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             vc2.push_back(arr[2][i] + arr[3][j]);       sort(vc2.begin(), vc2.end());       ll ans = 0;     for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)         {             ll a = arr[0][i] + arr[1][j];             ll b = lower_bound(vc2.begin(), vc2.end(), -a) - vc2.begin();             ll c = upper_bound(vc2.begin(), vc2.end(), -a) - vc2.begin();                  if (a + vc2[b] == 0)                 ans += c - b;         }     printf("%lld\n", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus