시간복잡도 줄이기 1) 중간에서 만나기 (+이분탐색)

1. 중간에서 만나기

---

• 알고리즘의 전체 탐색 범위를 반으로 나누어, 양쪽에서 동시에 탐색을 시작해 중간에서 만나는 방식으로 시간 복잡도를 줄이는 기법
• 예시
  • 00000000~99999999 비밀번호 풀기
    
    • 앞의 4자리와 뒤의 4자리를 따로 계산한 결과 A와 B를 합쳐서 정답이 되는지 확인하기
    • 10^8의 연산을 10^4 * 2 의 연산으로 줄여준다
  • A+B+C+D = 0 찾기
    • A+B = -(C+D) 로 계산하기
    • 모든 조합의 합을 계산 : n^2
    • C+D를 정렬한 후 A+B를 순환하면서 이분탐색을 하기 : O(N^2logN)
      • N^2사이즈의 A+B 배열을 돌면서 O(N^2)
      • N^2사이즈의 배열을 이진탐색 O(logN^2) 하기 -> O(N^2logN^2)
• !중요!
  • 메모리 제한을 항상 생각하고 쓰기
  • 이 방식은 메모리를 많이 사용하게 된다!

 

 

2. 문제

---

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

 

풀이

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

int n;
vector<int> board[4];
vector<int> sumA;
vector<int> sumB;
long long answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		board[0].push_back(a);
		board[1].push_back(b);
		board[2].push_back(c);
		board[3].push_back(d);
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			sumA.push_back(board[0][i] + board[1][j]);
			sumB.push_back(board[2][i] + board[3][j]);
		}
	}

	sort(sumB.begin(), sumB.end());

	for (const auto& a : sumA)
	{
		int target = -a;

		int st = lower_bound(sumB.begin(), sumB.end(), target) - sumB.begin();
		int en = upper_bound(sumB.begin(), sumB.end(), target) - sumB.begin();

		answer += (long long)(en - st);
	}

	cout << answer;
}