[백준 알고리즘][C++] 이분 탐색(binary search) - 7453번 합이 0인 네 정수

안녕하세요~

​

이번시간에는 7453번 합이 0인 네정수 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

 

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int A[4000];
int B[4000];
int C[4000];
int D[4000];
int N;
vector<int> sumOfCD;
vector<int> sumOfAB;
int main()
{
	long long int answer = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}
	//B와 C의 전체 합을 구함
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			sumOfCD.push_back(C[i] + D[j]);
		}
	}
	sort(sumOfCD.begin(), sumOfCD.end());
	//A와 B의 전체 합을 구함
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			sumOfAB.push_back(A[i] + B[j]);
		}
	}
	sort(sumOfAB.begin(), sumOfAB.end());
	
	for (int i = 0; i < sumOfCD.size(); i++)
	{
		int target = -sumOfCD[i];
		int start = 0;
		int end = sumOfAB.size()-1;
		//Lower bound
		while (start <= end)
		{
			int mid = (start + end) / 2;
			if (target > sumOfAB[mid])
			{
				start = mid + 1;
			}
			else 
			{
				end = mid - 1;
			}
		}
		int lowerbound = start;
		//Upper bound
		start = 0;
		end = sumOfAB.size()-1;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			if (target >= sumOfAB[mid])
			{
				start = mid + 1;
			}
			else 
			{
				end = mid - 1;
			}
		}
		int upperbound = start;
		answer += (upperbound - lowerbound);
	}
	cout << answer << endl;
}