[백준] 1072 게임

문제

• 게임 횟수 X 이긴 게임 Y 이 주어질 때, 최소 몇 판의 게임을 해야 승률 Z가 변하는지 구하기
  • 1 <= Y <= X <= 1,000,000,000
  • 승률은 백분율이고 소수점을 버린다. 예를 들어, X=53, Y=47이라면 Z=88이다.
• Z가 절대 변하지 않는다면 -1 출력

 

풀이

• 승률이 절대 바뀌지 않는 경우는, 처음 승률이 99% 이상일 때다.
• 이진 탐색으로 0 ~ X 까지의 범위에서 승률이 바뀌는 경우를 찾는다.

X, Y = map(int, input().split())
z = Y*100//X    # 처음 승률

if z >= 99:     # 승률이 절대 바뀌지 않는 경우
    print(-1)
else:
    answer = 0  # 정답
    # 이진 탐색
    s, e = 1, X
    while s <= e:
        m = (s+e) // 2

        if int((Y+m)*100//(X+m)) > z :   # 승률이 바뀌면
            e = m - 1
            answer = m 
        else:
            s = m + 1
    print(answer)

 

References

• 백준 1072
• 2023.04.29 오늘의 문제