<JUNGOL > 확률#5805

문제 : https://www.jungol.co.kr/problem/5805

무엇을 구하는 문제인가?

이미 X번 던져 Y번 앞면이 나왔다. 이때 몇번 앞면이 나와야 확률이 바뀌는 지 최소 횟수를 구하는 문제.

​

해결 전략

-n범위가 굉장히 큼으로 완전 탐색은 불가능하고, 이에 따라 이분탐색을 생각해볼 수 있다.

-현재 확률인 (y*100)/x를 변수now_p에 저장하고, ((y+mid)*100)/(x+mid)가 now_p에 근사할때 까지 이분탐색을 진행한다.

​

알고리즘

1. x, y를 입력받는다.

2. (y*100)/x를 변수now_p에 저장한다.

3. 2분탐색에서 필요한 low = 1, high = 2e9(20억 = 최대입력값의 2배)로 선언한다.

4. low <= high인 동안 반복

-mid = (low + high)/2

-((y+mid)*100)/(x+mid)가 now_p보다 작다면 -> low = mid + 1

-아니면 -> high = mid - 1

5. low 출력

​

※주의 할점

입력시 x == y이거나 정답 출력전 low가 x보다 크다면 -> -1출력

범위가 큼으로 long long으로 작성함

​

<소스 코드>

#include <stdio.h>

long long x, y;

int main()
{
	int i, j;
	scanf("%lld %lld", &x, &y);
	if (x == y) {
		printf("-1");
		return 0;
	}
	long long np = (y * 100) / x;
	long long low = 1, high = 2e9;
	while (low <= high)
	{
		long long mid = (low + high) / 2;
		long long n_np = ((y + mid) * 100) / (x + mid);
		if (n_np <= np) low = mid + 1;
		else high = mid - 1;
	}
	if (low > 2e9) printf("-1");
	else printf("%lld", low);
	return 0;
}

​