🖊️ 문제

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

---

🖊️ 풀이

여기서 조심해야 하는 점
1. X Y Z을 long long으로 설정
2. 1번이라도 패배하면 승률이 100%가 될 수 없음 -> z >= 99이면 -1을 리턴해줘야함
3. 무한루프로 일반 탐색하면 시간초과

전반적인 알고리즘은 매우 쉬우나,,
이분 탐색을 해야 한다 !

이분 탐색 (Binary Search)

범위 내 중간 값을 찾아서,
그 중간값(mid)이 target과 같은지 확인한다.
1. 같다면 -> mid = target
2. mid < target : 오른쪽으로 다시 탐색 (mid+1 ~ high) => low = mid + 1
3. mid > target : 왼쪽으로 다시 탐색 (low ~ mid - 1) => high = mid - 1

#include <iostream>
using namespace std;

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

	long long x, y;
	cin >> x >> y;

	long long z = 100 * y / x;
	int result = 0;

	if (z >= 99) {
		result = -1;
		cout << result << endl;
		return 0;
	}

	int low = 0;
	int high = 1'000'000'000;
	int mid, target;
	while (low <= high) {
		mid = (low + high) / 2;
		target = 100 * (y + mid) / (x + mid);
		if (z < target) high = mid - 1;
		else low = mid + 1;
	}
	result = low;

	cout << result << endl;
}