[백준] 1072 게임 with Python

📌 BOJ 1072 게임

💡 조건

1. 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

2. 형택이는 앞으로의 모든 게임에서 지지 않는다.
   형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

3. 게임 기록은 다음과 같이 생겼다.
   • 게임 횟수 : X
   • 이긴 게임 : Y (Z%)
   • Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

4. X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 문제
   첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

5. 1 ≤ X ≤ 1,000,000,000
   0 ≤ Y ≤ X

6. 수학, 이분탐색 유형의 문제

🔖 예제 및 실행결과

예제 1

10 8

실행결과 1

1

예제 2

100 80

실행결과 2

6

예제 3

47 47

실행결과 3

-1

예제 4

99000 0

실행결과 4

1000

예제 5

1000000000 470000000

실행결과 5

19230770

⌨️ 문제 풀이

1. 게임을 몇 판을 하면 승률이 변할지 구하는 문제이다.

2. X의 범위를 보면 하나하나 계산해서 찾을 수 없고, 이분탐색을 통해서 결과를 도출해야 한다는 것을 알 수 있다.

3. 또한 승률을 구하려면 당연히 소숫점 계산이 필요하다고 생각할 수 있지만, b 에 100을 곱하면 그렇게 하지 않아도 된다.

4. 이분탐색을 처음 시작할 때, left 에 해당되는 변수는 0으로 시작하고 right 에 해당되는 변수는 X, Y 중 큰 것을 골라 넣는다.

🖥 소스 코드

from sys import stdin

a, b = map(int, stdin.readline().split())
z = b * 100 // a

ans = int(1e11)
start, end = 0, max(a, b)

while start <= end:
    mid = (start + end) // 2
    res = (b + mid)  * 100 // (a + mid)

    if res != z:
        ans = min(ans, mid)
        end = mid - 1
    else:
        start = mid + 1

print(ans if ans != int(1e11) else -1)