[백준 31962] 등교

문제 출처 : https://www.acmicpc.net/problem/31962

 

이 문제는 2024년 정보올림피아드 1차대회 초등부 1번 문제입니다.

문제 이해하기

문제의 말이 조금 어렵게 느껴질 수 있지만 결국은 학교에 제시간에 등교를 하면서 가장 늦게 가는 버스를 타고 싶다는 것입니다. S는 버스를 타는데 걸리는 시간입니다. 즉 S가 가장 큰 것이 버스를 가장 늦게 타는 것입니다.

다음으로 생각해야 하는 부분이 버스가 정류장에서 학교에 도착하는 시간 T입니다. 학교에 도착하는 시간은 정류장에서 출발하는 시간 S와 학교에 도착하는 시간 T의 합계 입니다. S 와 T의 합계가 X분 이하라면 학교에 제시간에 도착할 수 있습니다.

결국 이 문제는 학교에 제시간에 도착하면서 가장 늦게 가고 싶다는 것이기 때문에 S + T의 합계가 X보다 작으면서 S가 가장 큰 경우를 찾는 문제 입니다. 만약 S + T가 X보다 작은 경우가 없다면 -1을 출력하면 됩니다.

예제 확인

예제 1번을 보면 첫 번째 버스는 2분뒤에 오고 1분이면 학교에 도착합니다. 총 3분이라는 시간이 걸리고 학교 도착까지 남은 시간은 8분이기 때문에 제시간에 등교가 가능합니다.

두 번째 버스는 6분뒤에 오고 학교까지 3분 걸립니다. 총 9분이 걸려 학교에 지각하게 됩니다.

마지막으로 세 번째 버스는 4분뒤에 오고 4분동안 이동하여 총 8분이 소요되며 제시간에 등교가 가능합니다.

첫 번째 버스와 세 번째 버스가 학교에 제시간에 등교가 가능하지만 정올이는 가장 늦게 출발하고 싶습니다. 따라서 4분뒤에 정류장에 오는 세 번째 버스를 타면 되고 답은 4를 출력하면 됩니다.

예제 2의 경우 30분이 남았는데 버스가 오는 시간 15분, 학교에 도착하는 시간 20분을 더하면 35분으로 학교에 제시간에 등교할 수 없어 -1을 출력합니다.

코드 작성

문제를 같이 풀어보겠습니다.

입력 받기

첫 번째 줄에 버스의 개수 N과 학교에 도착해야 하는 시간 X를 입력 받습니다.

그리고 다음줄부터 N개의 버스 정보를 입력 받습니다. 버스의 정보는 도착까지 남은 시간 S와 학교에 도착하는 시간 T를 입력 받습니다.

mii = lambda : map(int, input().split())

N, X = mii()

for _ in range(N):
    S, T = mii()

시간 계산

입력을 받았으니 학교에 도착하는 시간을 계산해야 합니다. bus라는 리스트를 만들어 버스의 시간을 저장해 줍니다. 시간은 버스가 정류장에 도착하는 시간 S와 버스가 학교에 가는데 걸리는 시간 T를 더하면 됩니다.

S + T의 값이 X보다 작은 경우에만 bus에 정류장에 도착하는 시간 S를 추가해 줍니다. 등교 시간에만 도착하면 되기 때문에 T는 따로 저장할 필요가 없습니다.

bus = []
for _ in range(N):
    S, T = mii()
    if S + T <= X:
        bus.append(S)

이 때 S + T의 값은 X와 같은 경우에도 bus에 추가를 해주어야 합니다. 예제 1의 세 번째 버스의 경우 S + T의 값이 8로 X와 같습니다. 이런 경우를 꼭 고려해 주어야 합니다.

가장 늦은 버스 찾기

bus라는 리스트에는 제시간에 등교가 가능한 버스들만 저장되어 있습니다. 여기에 정류장에 도착하는 시간 S만 저장되어 있습니다. 버스 리스트에 들어있는 데이터 중 버스가 가장 늦게 정류장에 도착하는 경우를 출력해 주면 됩니다. bus 리스트를 정렬하여 마지막 값을 출력해 줍니다.

if bus:
    bus.sort()
    print(bus[-1])
else:
    print(-1)

리스트를 sort로 정렬하면 오름차순으로 정렬됩니다. 따라서 가장 큰 값을 얻기 위해서는 리스트의 마지막 값을 출력해야 합니다. 따라서 bus[-1]을 출력하여 가장 마지막에 있는 값을 출력해준 것입니다.

내림차순 정렬이 익숙하다면 아래와 같이 작성해도 됩니다.

    bus.sort(reverse=True)
    print(bus[0])

전체 코드

전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())

N, X = mii()

bus = []
for _ in range(N):
    S, T = mii()
    if S + T <= X:
        bus.append(S)

if bus:
    bus.sort()
    print(bus[-1])
else:
    print(-1)