백준 1253번, 좋다 풀이

문제

BOJ 1253

풀이

$ i $번째 수를 만들기 위해 $ j $번째 수와 $ k $번째수를 구한다고 가정합시다.

순서쌍 $ (i, j) $를 모두 구하면 경우의 수가 $ {n}C_{r} $이 됩니다.

 

이 순서쌍에서 남은 $ k = (i - j) $를 이분 탐색을 사용하여 log 복잡도로 구해봅시다.

그리고, 이분 탐색을 사용하여 구한 $ k $가 $ i $ 혹은 $ j $와 겹치는 경우를 확인하여 추가로 탐색해야 합니다.

전체 시간복잡도가 $ O(N^2logN) $이 되므로 시간 내에 해결할 수 있습니다.

 

 

이 문제에서 유의해야할 점은 $ A_{i} $와 $ A_{j} $가 같더라도 서로 다른 수로 취급합니다.

 

문제의 질문에서 여러 테스트 케이스를 정리해두었으니 직접 푸는데 도움이 되길 바랍니다.

 

6
0 0 3 3 3 3

답: 4

11
0 1 2 3 4 5 6 7 8 9 10

답: 8

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

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

	int n; cin >> n;
	vl vec(n);

	for (auto &i : vec) cin >> i;

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

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;

			ll c = vec[i] - vec[j];
			auto it = lower_bound(vec.begin(), vec.end(), c);
			if (it < vec.end() && *it == c) {
				if (vec.begin() + i == it || vec.begin() + j == it) {
					int f = 0;
					for (auto k = it + 1; k < vec.end() && k < it + 4; k++) {
						int ki = k - vec.begin();
						if (*k == c && ki != i && ki != j) {
							f = 1;
							break;
						}
					}

					if (!f) continue;
				}

				ans++;
				break;
			}
		}
	}

	cout << ans;
}