[백준 31962] 등교 [Python]

문제

정올이는 수업에 지각하지 않기 위해 학교에 X분 이내로 도착해야 한다. 학교로 이동하려면 정류장에 정차하는 N개의 버스 중 하나를 선택하여 탑승해야 한다.

게으른 정올이는 최대한 늦게 버스를 타기 위해서 N개의 버스의 정보를 찾아보았다. 각 버스가 지금부터 몇 분 후에 정류장에서 출발하며, 정류장에서 출발한 버스가 학교에 도착하기 위해 몇 분이 걸리는지 알아낼 수 있었지만, 어떤 버스를 타고 학교에 갈지 아직 결정하지 못했다.

정올이를 위해서 학교에 지각하지 않는 시각에 도착하는 버스 중에서, 가장 늦게 출발하는 버스가 출발할 때까지 걸리는 시간을 구해주자. 학교에 지각하지 않도록 버스를 선택하는 방법이 없을 수도 있다.

입력

첫 번째 줄에 N과 X가 공백을 하나 사이에 두고 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐, 한 줄에 하나씩 정류장에서 버스가 출발할 때까지 걸리는 시간 S와, 버스가 정류장에서 학교까지 가는 데 걸리는 시간 T가 공백을 하나 사이에 두고 주어진다.

출력

학교에 X분 이내로 도착할 수 없다면, −1을 출력한다.

학교에 X분 이내로 도착할 수 있다면, 가장 늦게 출발하는 버스가 출발할 때까지 걸리는 시간을 출력한다.

---

풀이

N개의 버스 출발 시간( S )와 이동 시간( T )을 입력받아. X이내 도착할 수 있는 가장 큰 S를 찾는 문제다.

정답이 없는 경우 즉 X이내에 도착할 수 없는 경우에는 -1을 출력해야 한다.

이제 반복문을 돌며 문제의 조건을 만족하는 최대 S를 구하자.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/31962