[#1072] 게임

❓ Question

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

📖 Before Start

이진 탐색을 사용하여 최솟값을 도출해내는 문제였다.

이번 문제는 이진 탐색을 활용하여 범위 내 최솟값을 산출해야 하는 문제였다.
탐색의 시작과 끝을 정한 후, 이진 탐색을 통해 수월하게 정답을 맞추었다.

✒️ Design Algorithm

이진 탐색을 진행하기 위해 탐색의 시작과 끝을 먼저 정해야 한다.

현재 형택이가 플레이한 게임 횟수는 X 개고, 그 중에서 승리한 게임은 Y 개이다.
따라서 먼저 현재 승률을 구하고, 이후 몇 번을 이겼는지에 따라 변동될 승률을 구한다.
아래는 내가 문제를 풀기 위해 설계한 로직이다.

1. 이진 탐색의 시작과 끝을 1과 Y로 놓고 이진 탐색을 시작한다.
2. 중간 값 mid 만큼 승리한 게임을 더한 후, 전체 승률을 구한다.
3. 기존의 승률보다 현재 승률이 상승했다면, 탐색 종료 범위를 줄인다.
4. 기존의 승률과 현재 승률이 동일하다면, 탐색 시작 범위를 늘린다.

승률이 상승했다면 기존의 승률을 변동시킬 만큼 승리했다는 의미이므로, 끝 범위를 줄인다.
반대로 변동이 없다면 아직 승률을 변동시킬 만큼 승리하지 않았으므로, 시작 범위를 늘린다.

💻 Making Own Code

✅ Correct Code

import sys
from math import inf

X, Y = map(int, sys.stdin.readline().split())
current_win = Y * 100 // X

start, end = 1, X

result = inf
while start <= end:
    mid = (start + end) // 2
    next_win = (Y + mid) * 100 // (X + mid)
    # 승률이 올라갔다면, 그만큼 많이 이겼으므로 끝 범위 축소.
    if next_win > current_win:
        result = min(mid, result)
        end = mid - 1
    # 승률이 그대로일 경우, 더 많이 이겨야 하므로 시작 범위 증가.
    else:
        start = mid + 1

print(result if result != inf else -1)

부동 소수점을 정수로 변환하는 과정에서 발생하는 오차를 고려해야 했다.

처음에 승률을 구하는 식을 int( Y / X * 100) 으로 두었는데, 이것이 잘못된 값을 가져왔다.
따라서 굳이 / 연산자를 사용하지 않고, 몫만을 구하는 // 연산자를 통해 오류를 바로잡았다.

식은 맞았는데 계속 틀렸다고 나오길래 대체 뭐가 문제인가 했다

📖 Conclusion

📒 github Code link

https://github.com/RookieAND/BaekJoonCode

Python 에서 부동소수점을 정수로 변환하는 과정에서 오차가 날 수 있음을 유의해야 했다.
추후에는 이러한 일이 없도록 식을 더욱 꼼꼼히 작성해야겠다.