[백준] 1072 게임 python

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

1072번: 게임

확률 Z값을 구하고, s와 e의 중간값으로 만든 새로운 확률이 Z보다 큰 값을 찾으면 된다.

그리고 커지는 값중에 최솟값을 찾아야하니 s가 e보다 커지는 값을 종료 조건으로 반복문을 설정해서 이분탐색을 하면 된다.

 

def main():
    X, Y = map(int, input().split())
    Z = (Y * 100) // X

    s, e = 0, X
    while s <= e:
        m = (s + e) // 2
        mz = ((Y + m) * 100) // (X + m)
        if mz <= Z: s = m + 1
        else:       e = m - 1

    if s > X:
        print(-1)
    else:
        print(s)

if __name__ == '__main__':
    main()

처음에 최대 게임 회수가 X이고 돌릴수 있는 회수가 X-Y인줄 알았는데 그게 아니었다.

99 퍼센트 이상이 아니라면 탐색의 범위를 X(현재까지 진행한 게임의 횟수)로 설정하면 매우 큰 수가 아니더라도 탐색할수 있다.

예를들면 Y: 0~98, X: 100 이라고 했을때 Z = 0 ~ 98% 이다. 이때 1%를 올리기 위해선 최소 2번 이상 최대 100번이 된다. 그래서 현재까지 진행한 게임의 횟수(100)이 상한선으로 구할 수 있다. 그이상올라가도 99퍼센트가 되니 할 필요도 없다. 물론 처음 확률부터 99 퍼센트이거나 그 이상인 경우는 값이 바뀔수 없으니 -1을 만들어주면 된다.