[알고리즘] 백준 1590 - 캠프가는 영식

문제

캠프가는 영식

접근

1. 새로운 배열에는 버스 시작 시간을 시점으로 간격마다의 버스 시간표를 넣어준다.

2. 새로운 배열의 가장 마지막 버스가 내가 도착한 시점보다 이전이면 넘어간다

3. 이진 탐색을 사용해서 내가 도착한 시점과 가장 가까운 버스 시간표를 새로운 배열에 있는 값에서 찾아서 정답 배열 넣어준다.

4. 정답배열 ( 여기서는 res )에 데이터를 넣어줄땐 "  넣어지는 값 - 내가 도착한 시점의 시간 "  을 하여서 넣어준다.

5. 정답 배열이 있을때는 min 함수를 사용해서 최솟값을 넣거나 없으면 -1을 호출한다

 

풀이

import sys
input = sys.stdin.readline

N, T = map(int, input().split())
res = []
for _ in range(N):
    time, gap, n = map(int, input().split())
    li = [time+gap*i for i in range(n)]
    if li[-1] < T:
        continue
    start, end = 0, n-1
    a = 0
    while start <= end:
        mid = (start+end)//2
        if li[mid] >= T:
            a = mid
            end = mid-1
        else:
            start = mid+1
    res.append(li[a]-T)
print(min(res) if res else -1)