[Python, 이분탐색] 백준 1072 게임

접근방식
이 문제를 해결하기 위해 이진 검색을 사용합니다. 중요한 점은 'X'의 가능한 값이 크기 때문에 간단한 계산이 비효율적이라는 것이다. 따라서 이진 검색을 사용하여 승률을 높이는 데 필요한 최소 추가 게임 수를 효율적으로 결정할 수 있다.

문제풀이
초기 승률 Z = (100 * Y) // X를 계산합니다.
Z >= 99인 경우 백분율을 더 높이는 것은 불가능하며 -1을 반환
왼쪽 = 0 및 오른쪽 = X로 시작
중간점 계산: mid = (왼쪽 + 오른쪽) // 2.
새로운 승률 (100 * (Y + mid)) // (X + mid)가 Z를 초과하는 경우 결과를 mid로 업데이트하고 검색 범위를 왼쪽으로 조정

(right = mid - 1).
그렇지 않으면 검색 범위를 오른쪽(왼쪽 = 중간 + 1)으로 조정합니다.


코드구현

x, y = map(int, input().split())
z = (100 * y) // x
left = 0
right = x
res = x

if z >= 99:
    print(-1)
else:
    while left <= right:
        mid = (left + right) // 2
        if (100 * (y + mid)) // (x + mid) > z:
            res = mid
            right = mid - 1
        else:
            left = mid + 1
    print(res)

KEY POINT
- 이진 검색 사용 사례: 이 문제는 특히 큰 숫자를 처리할 때 특정 조건을 달성하는 데 필요한 최소 반복 횟수를 찾기 위해 이진 검색을 적용할 수 있는 방법을 보여쥼
- edge case: 이 솔루션은 Z >= 99인 경우 즉시 -1을 반환하여 승률을 향상시키는 것이 불가능한 경우를 설명
- 효율성: 이진 검색을 사용하여 가능한 솔루션 범위를 좁힘으로써 무차별 접근 방식의 비효율성을 방지

 

결론
이분탐색은 큰 입력 크기로 인해 직접 계산에 비용이 너무 많이 드는 문제에 접근하는 방법에 대한 좋은 예입니다.