백준 13423 ThreeDots c++ // 이분탐색

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

13423번: Three Dots

1. 의사코드

1. 2중포문으로 nC2를 함

2. mid값이 존재한다면, 간격이같은 순서쌍이 존재하는것임 -> cnt+1

3. 단, 간격이 홀수이면 mid가 x.5가 되므로 반드시 불가능함 -> continue 처리

4. 시간복잡도 : nC2 (1000*1000/2) * log 1000(이분탐색)

 

2. 전체코드

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int tc, n,dp[100004];

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

	cin >> tc;
	while (tc--) {
		cin >> n;
		vector<ll> v;
		int cnt=0;

		for (int i = 0; i < n; ++i) {
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}

		sort(v.begin(), v.end());
		for (int i = 0; i < n-1; ++i) {
			for (int j = i+1; j < n; ++j) {
				ll dist = v[j] - v[i];
				if (dist % 2) continue; //거리가 홀수다 -> mid가 x.5됨 -> 무조건 없음
				ll mid = v[i] + dist/2;
				
				//cout << v[i] << " " << mid << " " << v[j] << "\n";
				if (binary_search(v.begin(), v.end(), mid)) {
					cnt++;
				}
			}
		}
		cout << cnt << "\n";
	}
	

	return 0;
}