[백준 Python] 1072번 게임

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

1072번: 게임

 

문제정리

게임횟수 X, 이긴게임 Y 인 상태에서 승률은 Z 이다. ( 소수점 버림 )

이때 항상 이기는 게임 a 번을 했을 때 승률이 바뀌도록 해라.

 

문제풀이

Z = Y*100 // X 이다. 

*Z = (Y+a)*100 // (X+a) 에서 Z 와 *Z 가 달라지는 a 값을 구하면 된다.

 

Z 가 이미 99 라면 아무리 게임을 해도 100 으로 가지 못하며 Z 가 100 이라면 변화가 없으므로 예외처리를 해준다.

 

게임을 일단 해야 승률이 오른다.

얼마나 게임을 해야할지 생각해보면 1경기부터 쭉 올라가면서 최대 게임 수인 1.000.000.000 까지 경기를 해보면 된다. ( 브루트 포스 )

이를 간단히 풀기 위해 lo = 1, hi = 1000000000 으로 두고 이분탐색을 진행한다.

# 게임 횟수 X
# 이긴 게임 Y
# Z 는 승률 (소수점 버림)
# 게임을 몇번 더 해야 Z 가 변할까?

N, Y  = map(int, input().split())

Z = (Y * 100) // N


def judge(mid): # mid 로 확률이 바뀌나?
    return ((Y+mid)*100 //(N+mid)) <= Z

if Z >= 99:
    print(-1)
else:
    ans = 0
    lo = 1
    hi = 1000000000
    while lo <= hi:
        mid = (lo + hi) // 2
        if judge(mid): 
            lo = mid + 1
        else: 
            hi = mid - 1
            ans = mid
 
    print(ans)