7453 합이 0인 네 정수

완전탐색으로 접근하면 당연히 시간초과가 나는 문제이다. 왜냐하면 모든 경우를 탐색하는 시간 복잡도를 계산해보면, 4000^4이기 때문이다. 여기서 살펴볼 수 있는 문제는 탐색 횟수를 어떻게 줄이느냐이다.

문제의 조건을 다시 살펴보면 A+B+C+D=0을 만족하는 쌍을 구하여야 한다. 여기서 식을 조금만 수정해보자

A+B=-(C+D)로 바꿀 수도 있다. 이제 좌변과 우변의 경우의 수는 각각 4000^2으로 바뀌었다. 즉, 한 변을 미리 계산한다 하여도 4000^2 = 160만번의 횟수로 계산할만한 수치이다.

이를 컴퓨터에서 생각해보면, -(C+D)를 미리 계산해두어 배열에 저장해두는걸로 생각할 수 있다.

 

이제 남은건 -(C+D)를 계산해두었으니, A+B를 계산한 값과 비교하면 된다. 여기서 이분탐색의 개념을 적용해볼 수 있다. -(C+D) 배열에서 단순히 찾기만 한다면, O(N^2)의 복잡도를 갖지만 정렬하여 이분탐색을 한다면 O(logN)의 복잡도를 갖는다!

마지막으로 생각해볼 문제는 이분탐색에서 같은 값이 있을 때는 어떻게 처리하느냐이다. CPP의 STL에서는 정렬된 배열에 한해 이분탐색 기능이 구현된 함수를 제공한다.

lower_bound : 입력으로 들어온 값 이상이 나타나는 위치

upper_bound : 입력으로 들어온 값이 마지막으로 바뀌는 위치

해당 함수들을 통해 같은 값을 쉽게 처리해줄 수 있다.

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_SIZE 4000
int arr[4][MAX_SIZE];
int N;
int main()
{
	int result = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) 
		scanf("%d %d %d %d", &arr[0][i], &arr[1][i], &arr[2][i], &arr[3][i]);
	
	vector<long long> v;
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			v.push_back(arr[2][i] + arr[3][j]);
		
	sort(v.begin(), v.end());

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			long long temp = arr[0][i] + arr[1][j];
			int low = lower_bound(v.begin(), v.begin() + v.size(), -temp) - v.begin();
			int high = upper_bound(v.begin(), v.begin() + v.size(), -temp) - v.begin();

			if (-temp == v[low])
				//중복 값에 대한 처리
				result += high - low;
		}
	}
	printf("%d\n", result);
	return 0;
}