[백준 1072] 게임

요구사항

게임을 몇번 더 해야지 승률이 바뀌는가에 대한 문제

 

풀이

공식은 간단하다

게임 더한 횟수 : x

n, m 입력

초기 (m*100)/n과 게임 후의 (m+x)*100/(n+x)가 달라지는 시점을 찾아야 한다

주어진 수의 최대값이 10억이기 때문에

브루트 포스 X

모두 탐색하는데 원하는 수 찾는다 -> 이분 탐색

예외 처리는 

100%와 99%는 승률이 바낄수 없다(앞으로 계속 이긴다고 했으므로)

 

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAX = 1000000000;
int x;
ll n, m;
int flag = 0;
int main() {
	scanf("%lld%lld", &n, &m);
	x =  ((m*100) / (n));
	//cout << x << endl;
	if (x == 100 || x == 99) { 
		cout << -1 << endl; return 0;
	}

	ll Min = 0;
	ll Max = MAX;
	ll ans = 0;
	while (Min <= Max) {
	//	cout << "A" << endl;
		ll mid = (Min + Max) / 2;
		ll newx = ((m + mid) * 100) / (n+mid);
	//	cout << "X" << x << " newx" << newx << " mid " << mid << endl;
		//새로운 확률이 더 크다
		if (newx > x) {
			Max = mid - 1;
			
		}
		//새로운 확률이 더 작다
		else {
			Min = mid + 1;
		//	cout << "ans min " << Min << endl;
		}
	}
	cout << Min << endl;
	return 0;
}