[BOJ] Q1072 게임

[BOJ] Q1072 게임

Question

Language: Python

Difficulty: Silver 3

해당 문제의 경우 이분탐색을 이용하면 간단하게 풀리는 문제이지만, 여기서 중요한 부분은 float 연산 과정에서 발생하는 오차이다.

float 연산의 오차

print(1/3*100)  --> 33.33333333333333
print(1*100/3)  --> 33.333333333333336

이러한 연산의 문제가 발생하는 이유는 실수 연산 자체에 있다. 첫번째의 경우, 총 2번의 실수 연산을 처리하게 된다. 1/3 을 먼저 처리하고 다시 실수*100(정수)를 처리하게 되지만, 두번째의 경우 곱셈에서는 결과값이 정수이므로 실수연산이 아니며, 이후 나눗셈 과정에서 실수 연산이 발생하게 된다. 이처럼 실수 연산이 많아질 수록 오차 발생확률이 높아진다.

Solution

from math import inf

def solution():
    z=int(y*100/x)
    start,end=1,x
    min_games=inf

    while start <= end:
        
        mid=(start+end)//2

        if int((y+mid)*100/(x+mid)) >z:
            min_games=min(min_games,mid)
            end=mid-1
        else:
            start=mid+1

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

if __name__ == "__main__":
    x,y=map(int,input().split())

    solution()