[백준/Python] 1072번 게임

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

알고리즘

이진탐색을 이용하는 문제이다.

Z(승률)이 변하는 최소한의 게임 판수를 구하는데, 이때 승률이 변하지 않는 경우를 확인해주어야 한다.

Z 계산시 버림한다고 하였으므로, 99퍼 이상은 아무리 계속 승리를 해도 변하지 않으므로 Threshold를 Z = 99로 잡고 코드를 구성하였다.

게임 판수를 이진탐색의 right, 0판을 left로 잡고 이분탐색을 하면서 승률의 변동이 있는지 확인해준다. 

승률이 변했다면 판수를 더 줄여서 확인해 보아야하므로 r = mid-1을 통해 다시 이진탐색을 해주고, 승률이 변하지 않았다면 판수를 더 늘려서 확인해 보아야하므로 l = mid+1을 통해 이진탐색을 계속한다.

코드

import sys
input = sys.stdin.readline

x,y = map(int,input().split())

z = (y*100)//x #승률 계산

l,r = 0,x
ans = x
if z>= 99:
    print(-1)

else:
    while l<=r:
        mid = (l+r)//2
        if 100*(y+mid)//(x+mid) > z:
            ans = mid
            r = mid-1
        else:
            l = mid+1

    print(ans)