[백준] 1590 캠프가는 영식

1590 캠프 가는 영식

📄Description

영식이는 민식이와 함게 고속버스를 타고 캠프를 가야 하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.

영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 시각이 특점 시점을 기준으로 10분 후이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.

영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 기다려야 하는지 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 $T$가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각 $S_i$, 간격 $I_i$, 대수 $C_i$가 공백을 사이에 두고 주어진다.

  • $1 ≤ N ≤ 50$
  • $1 ≤ T ≤ 1,000,000$
  • $1 ≤ S_i ≤ 1,000,000$
  • $1 ≤ I_i ≤ 10,000$
  • $1 ≤ C_i ≤ 100$

출력 조건

• 첫째 줄에 영식이가 기다려야 하는 시간을 출력한다. 영식이가 도착하는 동시에 버스가 출발하면 정답은 0이다. 만약 버스가 없어서 캠프에 갈 수 없으면 -1을 출력한다. 정답은 231보다 작다.

예제 입력

input	output
1 285 150 50 10	15
1 123456 123456 10000 1	0
3 1 270758 196 67 904526 8930 66 121164 3160 56	121163
3 1000000 718571 2557 74 480573 9706 54 16511 6660 90	-1
5 395439 407917 8774 24 331425 4386 58 502205 9420 32 591461 1548 79 504695 8047 53	1776

---

🤔생각 정리

1. 배차시간과 버스 대수를 기준으로 버스 출발 시간 리스트를 만들어야겠네.
2. 이분탐색으로 영식이가 도착한 시간 이후로 온 버스 중 가장 기다리는 시간이 짧은 버스를 선택해야겠네.
3. 영식이가 탈 수 있는 버스가 없다면 -1을 출력해야겠네.

💡Pseudo Code💡

1. for bus in bus_list:
2. 		버스 출발시간 리스트 생성 range(s, s+l*c, l)
3. 		이분탐색으로 영식이 도착시간과 가장 가까운 출발시간 탐색
4. 		return 버스출발시간_best - t
5. 		버스 대기 시간 리스트에 추가
6. return min(대기시간) or 탈 수 있는 버스가 없다면 -1

---

🖥️코드화

# 입력
n, t = map(int, input().split())

# 버스마다 기다리는 최소시간 계산하는 함수
def count_time(bus):
    s, l, c = map(int, bus.split())
    b_list = list(range(s, s+l*c, l)) #버스 출발 시간 리스트
    lt, rt, time = 0, c-1, -1
    while lt <= rt:
        mid = (lt+rt)//2
        if b_list[mid] < t:
            lt = mid+1
        else:
            rt = mid-1
            time = b_list[mid]
    return time - t

times = []
for _ in range(n):
    res = count_time(input())
    if res >= 0:
        times.append(res)

# 출력
print(min(times) if times else -1) # 탈 수 있는 버스가 없다면 -1

---