[파이썬] 백준 1072번: 게임

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

1072번: 게임

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

def solution(x, y, z):
    left = 1
    right = 10**9
    if z == 100 or z == 99:
        return -1

    while left <= right:
        mid = (left+right) // 2
        new = int((y+mid)*100/(x+mid))
        if new > z:
            right = mid - 1
        else:
            left = mid + 1
    return left
print(solution(x, y, z))

 

이진분류를 사용하는 문제입니다.

1. x, y가 주어졌을 때 우선 이길 확률 (z)을 소수점 제거 후에 만들어줍니다.
2. 함수를 새로 설정합니다. left, right를 각 1, 10^9 (최대값 10억) 으로 설정합니다.
3. 100이나 99면 더 이상 변하지 않기 때문에 그대로 -1을 출력합니다.
4. 이진분류를 위해 while 문을 돌려줍니다. mid 설정 (left+right//2) 후,
mid값을 통해 new라는 새로운 확률값을 설정합니다.
(99부터 내려가면서 업데이트합니다. 만약 기존의 이길 확률 z보다 크면 right를 mid-1로 좁혀줍니다.
아니면 left를 밀어줍니다 (mid + 1))
5. 최종적으로 left를 출력합니다.