[ boj : 2428 ] 표절

www.acmicpc.net/problem/2428

2428번: 표절

문제 : 각 파일의 크기가 주어지고 F(i) <= F(j) 이고 F(i) >=0.9xF(j) 인 쌍을 구하여라

 

해설 : 이분탐색 문제입니다. 이분탐색은 풀때마다 헷갈리는 것 같아요 ㅠㅠㅠ 앞으로 꾸준히 풀 생각입니다.

먼저 n의 범위를 보고 우린 모든 가능한 경우의 수를 할 수 없다는 것을 알 수 있습니다.

그럼 다른 방법을 사용해야 되는데 조건을 보면 정렬해서 이분탐색 하세요...라고 주어지고 있죠.

이때, 0.9를 곱해야 되는데 우린 정수가 아닌 수들을 싫어합니다(저만 그런거 아니죠?)

그렇다면 양쪽에 그냥 10을 곱해버립시다.

 

10xF(i) >= 9xF(j) 으로 말이죠.

 

정렬을 하고 나서 어떤 한 수를 선택했으면 그 수보다 큰수는 볼 필요도 없습니다.

작은 수들 범위내에서 저 조건을 만족하면 더 작은 수로 넘어가고 조건을 만족하지 못하면 큰수로 올라갑니다.

 

주의할 점은 정답은 1+2+....+100000 이 될수도 있기때문에 꼭 long long 형을 써줍시다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll arr[100000];
ll solve(ll s, ll e);

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	sort(arr, arr + n);

	ll ans = 0;
	for (int i = 1; i < n; i++)
		ans += solve(0, i);
	cout << ans;
	return 0;
}
ll solve(ll s,ll e)
{
	ll mid;
	ll l = s, r = e;
	while (l <= r)
	{
		mid = (l + r) / 2;

		if (10 * arr[mid] >= 9 * arr[e])
			r = mid - 1;
		else
			l = mid + 1;
	}
	return e-l;
}