[이진 탐색 알고리즘] 게임 S3

기출 : BOJ #1072

이진 탐색의 핵심은 다음과 같다

 

1. 값을 변경할 변수 설정

2. 값을 변경하면서 체크할 함수 설정

 

이 문제에서는 추가적으로 진행할 게임 수가 변경할 값이고 승률 계산 함수가 체크할 함수이다

 

추가적으로 고려해야할 것은 승률 계산시 소수점 버리기 함수(trunc), 99퍼센트일때 예외 처리이다

 

from math import trunc
answer = -1
x, y = map(int,input().split())
z = trunc(y*100/x)

# 승률 계산
def check(val):
    return trunc((y+val)/(x+val)*100)

# 이진 탐색
def bs(st, en, target):
    global answer, z
    if st>en:
        return -1
    mid = (st+en)//2
    val = check(mid)
    if val <= z:
        bs(mid+1, en, target)
    else:
        answer = mid
        bs(st,mid-1,target)

bs(0,1000000000,z)
if z==99:
    print(-1)
else:
    print(answer)