[알고리즘] 백준 1072 게임 - S3

2024.10.09 풀이

import sys
input=sys.stdin.readline

x,y=map(int, input().split())

def bs(start, end, z):
    res=end
    while True:
        if start>end:
            return res
        mid=(start+end)//2 #10
        t=(100*(y+mid))//(x+mid) #90/110
        if t>z:
            end=mid-1
            res=min(res, mid)
        elif t<=z:
            start=mid+1

k=bs(0, 1000000000, (y*100)//x)
if (y*100)//x>=99:
    print(-1)
else:
    print(k)

• 추가해야하는 값들에서만 이분탐색을 진행해야한다는 포인트는 잡았으나
• 아래 풀이와 같이 승률이 크거나/아니거나로 나누어 생각할 수 있다는 점!

다른 풀이

x,y=map(int,input().split()) 
z=(100*y)//x 
left=0 
right=x 
res=x 
if z>=99: 
    print(-1)
else: 
    while left<=right: 
        mid=(left+right)//2 
        if (100*(y+mid))//(x+mid)>z: 
            res=mid 
            right=mid-1 
        else: 
            left=mid+1
    print(res)

check point

• 부동소수점 이슈
  - int(y/x*100) -> X
  - (100*y)//x -> O
• 승률 이슈
  - 승률이 99%부터는 더이상 오르지 않음