[Silver IV] 캠프가는 영식 - 1590

문제 링크

성능 요약

메모리: 31388 KB, 시간: 44 ms

분류

이분 탐색, 브루트포스 알고리즘, 수학

문제 설명

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

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

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

입력

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

출력

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

---

풀이

아이디어

아이디어 자체는 간단하다. 버스 도착 시간을 간격별로 버스 대수만큼 리스트를 만들어준다. 이때 만들어준 리스트는 오름차순이 보장되므로 따로 정렬 할 필요는 없다.

버스 도착 정보 리스트를 이분탐색 하고, 영식이가 버스정류장에 도착하는 시간을 기준으로하여 이분 탐색 결과가 버스 정류장 도착 시간보다 크되, 차이가 가장 작은 경우에 그 차이를 return 해준다.

버스가 많을때에는 그 중 가장 작은 경우를 정답으로 한다.

코드

첫번째 시도

import sys
input = sys.stdin.readline


def bi_search(lst, arrival_time, start, end):
    while start + 1 != end:
        mid = (start + end) // 2
        if lst[mid] > arrival_time:
            end = mid
        
        elif lst[mid] < arrival_time:
            start = mid
        
        else:
            break
    
    s = lst[start] - arrival_time
    e = lst[end]- arrival_time
    try:
        return min(filter(lambda x: x >= 0, [s, e]))
    except:
        return -1



n, t = map(int, input().split())
result = 1e9
for i in range(n):
    start_time, term, cnt = list(map(int, input().split()))
    chart = [start_time + term * i for i in range(cnt)]
    result = min(result, bi_search(chart, t, 0, len(chart) - 1))
print(result)

첫번째 아이디어의 구현은 start와 end를 비교하여 둘 중에 음수가 있는 경우를 제외하고 가장 작은 값을 반환하도록 하였으며, 모두 음수인 경우 예외 처리를 통해 -1을 출력하게 하였지만 틀렸습니다를 반환 받았다.

두번째 시도

import sys
input = sys.stdin.readline


def bi_search(lst, arrival_time, start, end):
    if lst[-1] < t:
        print(-1)
        exit()
    x = 0
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] >= arrival_time:
            end = mid - 1
            x = mid
        
        elif lst[mid] < arrival_time:
            start = mid + 1
        
        else:
            break
    # print(lst, lst[start], lst[mid], lst[end])
    return lst[x] - arrival_time


n, t = map(int, input().split())
res = []
for i in range(n):
    start_time, term, cnt = list(map(int, input().split()))
    chart = [start_time + term * i for i in range(cnt)]
    res.append(bi_search(chart, t, 0, len(chart) - 1))
# print(res)
print(min(res))

두번째 아이디어는 전체적인 흐름에서 비슷하지만 버스의 마지막 도착시간보다 영식이의 버스정류장 도착시간이 크다면 -1을 반환하고 프로그램을 종료하게 하였고, 나머지는 같은 매커니즘이다.

참고한 코드

N, T = map(int, input().split())
res = []
for _ in range(N):
    t, d, n = map(int, input().split())
    li = [t+d*i for i in range(n)]
    if li[-1] < T:
        continue
    s, e = 0, n-1
    a = 0
    while s <= e:
        m = (s+e)//2
        if li[m] >= T:
            a = m
            e = m-1
        else:
            s = m+1
    res.append(li[a]-T)
print(min(res) if res else -1)

위 코드는 정답 코드를 참고한 것인데, 두번째 방법과 다른점은 a라는 변수를 사용하여 영식이 버스정류장에 도착한 시간보다 중앙 탐색값이 크다면 a에 중앙 인덱스를 저장하고, 범위를 좁혀나간다.
이후 리스트에 최솟값을 저장하고 마지막에 여러 버스의 최소값을 출력한다.

---

회고

이 문제를 푸는데 약 1시간 정도 소요되었고, 코드를 참고하지 않았으면 더 걸렸을 문제라서 "풀지 못한 문제"가 되었다는게 아쉽다.
두번째 코드가 실패한 원인을 아직 파악하지 못했는데 파악후 내용을 추가하도록 하겠다.

반례를 찾아나가는 방법을 연습해야 할 것 같다.