[백준 1072] 게임(python)

1. 아이디어

우리가 찾아야하는 답은 승률이 변하기 위한 최소 게임 판 수 이다. 따라서 최소 게임 판 수를 이분탐색으로 찾아본다.

형택이가 앞으로 하는 게임은 전부 이기는 게임이다. 따라서 승률이 변하는 것은 승률이 오른다는 것을 의미한다. 반면, 아무리 게임을 많이 해도 승률이 전혀 오르지 않을 경우(-1를 출력하게되는 경우)를 이분탐색의 관점에서 생각해보자. 이는 이분 탐색을 진행한 결과 left 값이 초기에 설정된 right 값보다 크다는 것을 의미한다.

초기 설정할 left, right의 값을 구해야한다. left는 최소 1판의 게임을 하므로 1이라는 것을 알고 있다. 근데 right는 어떻게 구할까. 사실 나는 이 문제에서 찾지 못해서 최대 할 수 있는 게임판 수를 10억으로 임의 설정했다. 1번째 문단을 고려할 때, left가 10억이 넘어가버리면 승률를 올릴 수 없다고 판단하여 -1를 출력하게된다.

이번에는 승률이 오를 수 있는 상황을 생각해보자. 추가적인 게임 판수를 진행했음에도 승률이 오르지 않는다면 게임 판 수를 늘리면된다. 다시 말해 left = mid + 1이다. 반대로 승률이 올랐다면, 판 수를 한번 줄여보자. 왜냐하면, 우리가 원하는 것은 승률이 변할 수 있는 최소 판 수이기 때문이다. 이 과정을 이분탐색으로 구현한다.

2. 코드

import sys

x, y = map(int, sys.stdin.readline().rsplit())

INF = int(1e9)
left = 1
right = INF
win_rate = y*100 // x 
answer = INF
   
while left <= right:
    mid = (left+right) // 2
    games = x + mid
    wins = y + mid
    k = wins*100 // games
       
    if k == win_rate: left = mid + 1
    else:
        answer = min(answer, mid)
        right = mid - 1

if left > INF: print(-1)
else: print(answer)