[파이썬] 프린터 출력 / 이진탐색

문제

John과 Mary는 "J&M 출판사"를 설립하고 낡은 프린터 2대를 구입하였다.

그들이 첫번째로 성사시킨 거래는 N개의 페이지로 구성된 문서를 출력하는 일이었다.

그들이 구입한 두 대의 프린터는 각기 다른 속도록 문서를 출력하고 있다고 한다. 하나는 한 페이지를 출력하는 데 X초가 걸리고 다른 하나는 Y초가 소요된다고 한다.

John과 Mary는 두 대의 프린터를 이용하여 전체 문서를 출력하는 데 드는 최소한의 시간이 알고 싶어졌다.

-> 입력과 출력
입력데이터의 첫번 째 라인은 테스트케이스의 갯수를 뜻하고 그 갯수만큼의 라인이 추가로 입력된다. 
추가되는 각 라인은 세 개의 정수값 X Y N 으로 구성된다. X는 첫번째 프린터가 한 페이지를 출력하는 데 드는 소요시간, 
Y는 두번째 프린터가 한 페이지를 출력하는 데 드는 소요시간을 뜻하고 
N은 출력할 문서의 총 페이지 수를 의미한다. (단, 출력할 문서의 총 페이지 수는 1,000,000,000개를 초과하지 않는다.)

두 가지 이진탐색을 작성했다.

1. 시간 기준 이진탐색

def solution(X, Y, N):
    start=0
    end=max(X,Y)*N
    result=end
    
    while start<end:
        mid=(start+end)//2
        pages=mid//X + mid//Y #mid시간에 출력되는 페이지 수
        if pages<N:
            start=mid+1
        else:
            end=mid-1
            result=min(end, result)
    
    return result

 

2.  페이지 기준 이진탐색

def BS(X, Y, N):
    lower = 0
    upper = N
    
    while lower < upper:
        if max(upper * X , (N - upper) * Y) < max(lower * X, (N - lower) * Y):
            # upper 쪽이 더 유리한 상황
            lower = (lower + upper + 1) // 2
        else:
            upper = (lower + upper) // 2
   
    return max(upper * X, (N - upper) * Y)