[알고리즘] 백준 13423번: Three Dots (C++)

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

13423번: Three Dots

이 문제는 3가지 점 모두 브루트 포스로 구하면 시간 초과가 난다.

Worst Case: O(n^3) => O(1000^3)

---

솔루션

두 점까지는 브루트 포스로 구하고, 나머지 한 점은 2번째 점과 1번째 점의 차이를 만족하도록 고르는 점과 2번째 점의 차이가 같은 점을 이분 탐색으로 구해주었다.

>> 이분 탐색을 위해 입력받은 점들을 정렬해주었다.

 

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

int T;

int sol(vector<int>& v, int first, int second) {
	int dif = v[second] - v[first];
	int low = 0;
	int high = v.size() - 1;

	// Binary Search
	while (low <= high) {
		int mid = (low + high) / 2;
		int findValue = v[mid] - v[second];

		if (findValue == dif) {
			return 1;
		}
		else if (findValue > dif) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return 0;
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n;
		cin >> n;
		vector<int> dots;
		int value;
		for (int i = 0; i < n; i++) {
			cin >> value;
			dots.push_back(value);
		}
		sort(dots.begin(), dots.end());

		int resultCnt = 0;
		// Brute-Force
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				resultCnt += sol(dots, i, j);
			}
		}
		cout << resultCnt << '\n';
	}
	return 0;
}