알고리즘/백준

BOJ 1072 게임 / C++

내이름은 킹햄찌 2022. 12. 4. 12:39

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

 

1072번: 게임

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시

www.acmicpc.net

아이디어

이진탐색을 이용하였습니다.

 

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


long long X, Y, Z;

void input() {
	cin >> X >> Y;
	Z = Y * 100LL / X;
}


bool check(long long mid) {
	long long nY = ((Y+mid) * 100LL / (X+mid));
	return nY > Z;
}

void solution() {

	long long l = 0;
	long long r = MAX;
	//승률이 99이상이면 바뀌지 않음
	if (Z >= 99) {
		cout << -1;
		return;
	}
	while (l + 1 < r) {
		long long mid = (l + r) >> 1;
		//승률이 높아졌을때 게임의 수 줄임
		if (check(mid)) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout <<r;
}
int main(void) {
	input();
	solution();
}