[백준] 1072번 게임

💡문제접근

• 형택이가 시행한 게임 횟수 X의 범위는 1 ≤ X ≤ 1,000,000,000으로 브루트포스 알고리즘으로 접근하면 엄청난 시간이 발생하게 된다. 따라서 이분 탐색으로 접근해야한다고 생각했다.
• 질문게시판에 있는 내용을 참고했는데 100을 먼저 따로 곱해주거나 아니면 이긴 횟수 Y에 먼저 곱해주는 방식이 정확도를 높일 수 있다고 하는데 정확한 이유는 잘 모르겠다.
• 우선 최대 1,000,000,000번 게임을 할 수 있으므로 중간값부터 확인해서 만약 기존 확률과 새로 게임을 몇 번 더 한 다음 나오는 확률을 trunc를 사용하여 소수점을 절사해 비교하여 답을 찾아내는 방식으로 코드를 작성했다.
• 문제에서 형택이는 앞으로의 모든 게임에서 지지 않는다고 했기 때문에 만약 형택이의 승률이 100%라면 절대 변하지 않으므로 -1을 출력하고 만약 형택이의 승률이 99%라면 1판 증가하면서 이긴 게임의 횟수가 1판 증가하므로 형택이의 승률이 절대로 변할 수 없으므로 -1을 출력하였다.

💡코드(메모리 : 32672KB, 시간 : 36ms)

import sys
input = sys.stdin.readline

import math

X, Y = map(int, input().split())
Z = math.trunc((Y * 100 / X))

def binary_search(target):
    start = 0
    end = 1000000000
    while True:
        if start >= end:
            break
        mid = (start + end) // 2
        new_Z = (((Y + mid) * 100) / (X + mid))
        if math.trunc(new_Z) > math.trunc(target):
            end = mid
        else:
            start = mid + 1
    return end
if Z >= 99:
    print(-1)
else:
    print(binary_search(Z))

💡소요시간 : 21m