[백준]1072_게임

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

Solved

✔ 수학, 이분탐색
✔ 애초에 게임에서 진 적이 있으면 승률 100%을 만들 수 없기에 z>=99일 때 return -1
✔ 10억번을 일일히 찾으라는 문제는 없을테니 이분탐색을 바로 떠올리자

using namespace std;
#include <iostream>
#define MAX 1000000000;

int main() {
	double x, y;
	cin >> x >> y;
	int z = y * 100 / x; // z%

	if (z>= 99) {
		cout << "-1\n";
		return 0;
	}

	int bottom = 1, top = MAX;
	int answer = MAX;
	while (bottom <= top) {
		int mid = (bottom + top) / 2;
		int nz = (y + mid) * 100 / (x + mid);
		if (z < nz) {
			if (mid < answer) answer = mid;
			top = mid - 1;
		}
		else bottom = mid + 1;
	}
	cout << answer << '\n';
	return 0;
}