백준[ 19592 | Python ] 장난감 경주

문제

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

풀이

먼저 부스터를 쓰지 않아도 되는 경우를 먼저 계산해주어 고려 대상에서 제외한다.
먼저 생각할 점은 빠르기의 기준을 무엇으로 삼을 것인가 였다.

시속으로 바꾸어 계산하면 ‘나’의 장난감 시속이 1m/s인 경우 수가 너무 작아져 복잡해지므로
(동시에 ‘나’의 장난감이 주행할 트랙도 줄어든다.) 트랙 X를 통과할 수 있는 시간으로 기준을 삼았다.

통과 시간을 기준으로 삼았으니 이전에 뽑아낸 winner(가장 시속이 빠른 장난감)을 시간으로 바꿔준다.
그 다음은 부스터를 사용한 ‘나’의 장난감이 통과하는데 걸리는 시간을 알아내기 위해 booster 함수를 구현 했다.
booster함수의 출력은 ‘나’의 장난감이 실제로 달릴 거리(트랙(X)-1초동안 부스터를 사용한 거리(Z))를 속도v로 나눠주고 1(부스터를 사용한 시간)을 더해준 값 = 시간이다.

그 다음은 이분탐색을 사용해서 winner와 ‘나’의 장난감의 통과 시간을 비교해 결과를 낸다.

for _ in range(int(input())):
    n,x,y = map(int,input().split())#참가자 수, 트랙의 길이, 부스터 한계치
    toys = list(map(int, input().split()))# 속도

    winner = max(toys)    
    if toys.count(winner) == 1 and toys[n-1] == winner:
        print(0)
        continue
    else:
        winner = x/winner

        def booster(v, bv):
            dist = x-bv
            return (dist/v)+1

        l, r = 0, y
        time = x/toys[-1]

        while True:
            m = (l+r)//2
            boost = booster(toys[-1], m)
            if l > r:
                break
            if boost >= winner:
                l = m+1
            else:
                r = m-1
        if l > y:
            print(-1)
        else:
            print(l)

생각 & 정리

5번째 테스트케이스가 애를 먹였다.
알고보니 정수형(//)으로 나눠주던 값 들을 소수형(/)으로 나눠주니 소수점 아래까지 비교해서
통과할 수 있는 시간을 비교해야했다.

바로 코드를 치기보다는 문제에 따라 테스트케이스를 먼저 분석하는 것이 필요할 것 같다.