알고스팟 승률올리기 (RATIO) 문제 파이썬으로 풀기

승률을 1% 올리게 되는 가장 적은 연승 횟수를 구하는 문제이다.

 

이진탐색을 생각해 낸다면 매우 쉬운 문제가 될 것이고, 아니라면 고생할 것이다.

물론 난 후자였고, 그래서 이것저것 고민해보다가 문제 분류에 이진탐색이라고 있는것을 보고 이진탐색을 적용하여 문제를 해결했다.

# ratio
maxwin = 2000000000  # 최대 승리
case = int(input())
for i in range(case):
    n, m = map(int, input().split())
    result = 0  # 결과
    nowrate = (m * 100) // n  # 현재 승률
    if nowrate >= ((m + maxwin) * 100) // (n + maxwin):  # 최대 연승 했을때도 승률이 변하지 않는경우
        result = -1
    else:  # 이진탐색
        left = 0
        right = maxwin
        while left + 1 < right:
            mid = (left + right) // 2  # 중간값
            if nowrate >= ((m + mid) * 100) // (n + mid):  # 현재 승률보다 높지 않으면
                left = mid
            else:  # 현재 승률보다 높아지면
                right = mid
        result = right
    print(result)

코드 자체는 간단하다.

 

느낀점:

1. 파이썬에서 몫을 구할때 // 연산자를 이용하면 되는데, 그것을 잊고 int 함수를 사용하다가 계속 오답이 뜨는 것을 보고 생각이 나서 죄다 //를 쓰게 바꾸니 바로 정답이 떳다. 허탈하다. 다른 사람들 코드를 보면 import math 후 math.floor 나 math.ceil도 쓰긴 하던데 //이 편한거같다.