1072번: 게임 / silver 3 / 이분탐색

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

1072번: 게임

 

시간 초과

'''
1072번: 게임 / silver 3
'''

game, win = map(int, input().split())
odds = int(win / game * 100)
new_odds = -1
if odds == 100:
    print(-1)
else:
    x = 1
    while new_odds != odds + 1:
        new_odds = int((win + x) / (game + x) * 100)
        x += 1
    print(x - 1)

 

정답

'''
1072번: 게임 / silver 3 / 이분탐색
'''

game, win = map(int, input().split())
rate = (win * 100) // game
if rate >= 99:
    print(-1)
else:
    res = 0
    start = 1
    end = game
    while start <= end:
        mid = (start + end) // 2
        new_odds = (win + mid) * 100 // (game + mid)
        if new_odds <= rate:
            start = mid + 1
        else:
            res = mid
            end = mid - 1
    print(res)

 

이분 탐색 문제

 

- start, mid, end 통해서 조건에 맞는 최솟값 찾기

 

 

 

부동 소수점 오차 주의

 

- Python 에서 승률 계산 시 올바른 계산 방법

rate = (win * 100) // game 

rete = int((win * 100) / game)

 

- 잘못된 방법

rate = int(win / game * 100)