[백준] 1072번 게임

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

• 시간 초과가 발생했던 코드

# 1072 : 게임

import sys
input = sys.stdin.readline

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

new_z = z
count = 0
while z == new_z:
    x += 1
    y += 1
    new_z = int((y / x) * 100)
    count += 1
    if new_z != z:
        print(count)
    elif x == y:
        print(-1)
        break

아마 1씩 증가해서 승률을 다시 측정해서 시간 초과가 발생한 것 같다.

구글링을 해보니 이진 탐색을 통해 문제를 해결한 경우가 많았다. 찾아보니 내가 놓친 히든 케이스가 존재했는데, 승률이 99%인 경우에는 한번이라도 졌었기 때문에 승률이 절대 100%가 될 수 없다.

그리고 실수 연산은 부정확 할 수가 있어서 int(y / x) * 100 대신 y * 100 // x 으로 하면 통과 된다고 한다.

• 이진 탐색을 이용한 풀이

# 1072 : 게임

import sys
input = sys.stdin.readline

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

# 승률이 절대 오르지 않을 경우
if z >= 99:
    print(-1)
else:
    answer = 0
    start, end = 1, sys.maxsize

    while start <= end:
        mid = (start + end) // 2
        new_z = (y + mid) * 100 // (x + mid)

        # 원래 승률보다 작거나 같을 경우
        if new_z <= z:
            start = mid + 1
        # 승률이 변한 경우(원래 승률보다 큰 경우)
        else:
            answer = mid
            end = mid - 1
            
    print(answer)

Uploaded by Notion2Tistory v1.1.0