[2일차] 시간복잡도 H - 1072: 게임

실버 Ⅲ

 

#include <iostream>
using namespace std;

int main() {
	long long X, Y, Z;
	scanf("%lld%lld", &X, &Y);
	Z = (Y * 100) / X;
	if (Z >= 99) {
		printf("-1");
		return 0;
	}

	int low = 0;
	int high = X + 1;
	int moregame;
	int ans = X + 1;

	while (low + 1 < high) {
		moregame = (low + high) / 2;
		long long newZ = ((Y + moregame) * 100) / (X + moregame);
		if (newZ > Z) {
			//그 이상으로 너무 큼
			//-> moregame 줄여야함
			//여기서 최소값 구해야함
			high = moregame;
			if (ans > moregame) ans = moregame;
		}
		else {
			//너무 작음
			//-> more game 키워야함
			low = moregame;
		}
	}
	printf("%d", ans);
}

어떤 구간이나.. 부분에 관한 것이 아니므로

투 포인터가 아니고 일단...

 

F F ... F F T T T ... T

일 테니까 여기서 T의 lower bound를 구하고 싶은 것

-> 이분탐색

 

어려웠던 점은.. 승률이 99%이면 절대 변하지 않을 거라고는

바로 생각이 안 들어서..

이런 부분은 수식으로 더 정확하게 풀었으면 좋았겠다

corner case라고 100%일 때만 생각했네