백준 7453. 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

 

4개 배열이 주어진다.

 

1. 1번 2번 배열을 합쳐 나올수 있는 모든 원소들을 A 배열에 저장하고, 3번 4번 배열을 합쳐 나올수 있는 모든 원소들을 B에 저장한다.

 

2. A, B 배열을 오름차순 정렬한다.

 

3. A배열의 원소가 a라면 B의 원소중 -a가 있다면 둘이 합쳐 0이므로 조건을 만족한다. 

A배열과 B배열의 최대 크기는 4000*4000 = 16000000 이다. 

B배열에서 -a값을 직접 일일이 찾는다면 알고리즘의 총 시간복잡도는 16000000 * 4000 이 되므로 시간초과다. 

이분탐색 upper_bound와 lower_bound를 이용하면 16000000 * log(4000) 이 된다.