[ BOJ 1072 ] 게임(Python)

문제

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

예상치 못했던 실수 나눗셈,,, 때문에 광광 울었던 문제!!! 🤢
사탕 가게 문제에서도 실수 부동소수점 때문에 헤맸었다.

문제 풀이

게임 횟수 x, 이긴 게임 y일 때 승률은 z 이다.
앞으로 몇 회를 더 이겨야 승률이 변화할 지 풀면 된다.

0. 승률 구하기

victory = y * 100 // x

🔥 처음에 int(y / x) * 100 로 승률을 계산했었다. 그런데 채점이 100% 까지 됐다가 별안간 틀렸다고 뜨는 것이다 ㅠ
🔥 알고보니 실수 연산은 부정확 할 수 있기 때문에 주의해야 한다고 한다.
따라서 y * 100 // x 이렇게 계산을 해주니 통과할 수 있었다.

29/50=0.58과 29/50*100=57.9999999
https://www.acmicpc.net/board/view/68226

[백준] 1072: 게임 파이썬 리뷰 - 연산 오류, Y100//X, int(Y/X100)
https://ahn3330.tistory.com/110
실수의 연산은 부정확할 수가 있으므로 사용에 주의를 해야합니다.

(무한 소수가 나올 수 있지만, 컴퓨터 연산의 메모리는 이를 정확히 커버할 수 가 없으므로 예상과는 다른 결과가 나올 수 있음)

1. 이분 탐색 범위 정하기

l, r = 1, x

이제 와서 보니 X의 범위는 1 ≤ X ≤ 1,000,000,000 인데
r의 값이 x이면 안되지 않나 .. ?
r은,, 1000000000,, 이여야 되는 거 아닌가 , , , ?
근데 왜.. 맞은건지... ,.? 의문.. 🤔

2. mid번 이겼을 때 승률 구하기

mid = (l + r) // 2

curr_vic = (y + mid) * 100 // (x + mid)

3. 승률 비교해서 범위 줄이기

if curr_vic > victory:
     ans = min(mid,ans)
     r = mid - 1
else:
     l = mid + 1

mid번 이겼을 때 승률이 처음 승률보다 클 경우,
ans 변수에 더 작은 mid 값을 넣어주고 최댓값 범위를 줄여준다.
(최댓값 범위 감소 = mid 값 감소 = 승률 감소)

반대의 경우엔 최솟값 범위를 늘려준다.
(최솟값 범위 증가 = mid 값 증가 = 승률 증가)

코드

import sys
input = sys.stdin.readline

x, y = map(int, input().rsplit())
victory = y * 100 // x
ans = sys.maxsize
l, r = 1, x
print("[victory]:", victory)

while l <= r:
    mid = (l + r) // 2

    curr_vic = (y + mid) * 100 // (x + mid)
   
    if curr_vic > victory:
        ans = min(mid,ans)
        r = mid - 1
    else:
        l = mid + 1

if ans == sys.maxsize:
    print(-1)
else:
    print(ans)