[파이썬, Python] 백준 1072: 게임

문제

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

1072번: 게임

코드

x, y = map(int, input().split())
z = (y * 100) // x

if z >= 99:
    print(-1)
else:
    ans = 0
    start = 1
    end = x
    
    while start <= end:
        mid = (start + end) // 2
        if (y + mid) * 100 // (x + mid) <= z:
            start = mid + 1
        else:
            ans = mid
            end = mid - 1
            
    print(ans)

설명

우선 기존 승률이 99퍼센트 이상이라면 어떻게 해도 100퍼센트에 도달이 불가능하기 때문에 제외해 준다.

그 외의 경우를 생각해야 하는데,
브루트포스로 해결하게 되면 입력 값이 10억이기 때문에 타임아웃이 난다.

따라서 이분 탐색으로 범위를 빠르게 좁혀서 탐색한다.

시작 지점은 1로 정해주고
끝 지점은 x로 정한다.
x인 이유는 승률이 98퍼센트 일 때,
x회 더 진행하게 되면 99퍼센트가 되기 때문에 최댓값은 x이다.

이후 이분 탐색을 진행해 준다.

만약 새로 계산된 승률이 기존 승률보다 작거나 같다면
start를 갱신해 준다.

그렇지 않다면 현재의 승률이 더 높은 셈이므로 정답을 우선 갱신해 주고
end를 갱신해 준다.

탐색을 마치고 최종적으로 ans를 출력한다.