[BOJ] 1590 - 캠프가는 영식 (Python)

 

 

아이디어

 

버스 출발 시간을 구하여 정렬한 후, 이분 탐색으로 탈 수 있는 가장 빠른 버스 출발 시간과의 차이를 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N, T = map(int, input().split())
    bus = set()
    for _ in range(N):
        S, I, C = map(int, input().split())
        for i in range(C):
            bus.add(S+I*i)
    bus = sorted(bus)
    if T > bus[-1]:
        print(-1)
    else:
        s = 0
        e = len(bus)-1
        while s <= e:
            m = (s+e)//2
            if bus[m] > T:
                e = m-1
            elif bus[m] < T:
                s = m+1
            else:
                print(0)
                return
        print(bus[s]-T)

solution()