백준 1253번 [좋다]

투 포인터, 이분탐색

 

시간복잡도 n ㅡ> logn 만들 때 고려

시작 포인트 잡기

포인터 이동규칙 세우기

종료 조건 만들기

포인터가 경계값에 있을 때 따지기

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define tpi tuple<int, int, int>
#define tpl tuple<ll, ll, ll>
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define MOD 100000007
using namespace std;

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

	vector<ll> v;
	ll n;
	cin >> n;
	ll start = 0;
	ll end = n-1;
	ll res = 0;

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

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

	for (ll i = 0; i < n; i++) {
		start = 0;
		end = n - 1;
		while (start != end) {
			if (v[start] + v[end] < v[i]) {
				start++;
			}
			else if (v[start] + v[end] > v[i]) {
				end--;
			}
			else {
				if (i == start) {
					start++;
				}
				else if (i == end) {
					end--;
				}
				else {
					res++;
					break;
				}
			}
		}
	}
	
	cout << res;

	return 0;
}