루미 알고리즘

#1092브론즈등교등교

KOI 2024 1차코딩초등부 1번출제 이인복이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

등교

원제: 등교

문제

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

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

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

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤1001 \le N \le 100
  • 2≤X≤2002 \le X \le 200
  • 각 버스에 대해, 정류장에서 버스가 출발할 때까지 걸리는 시간을 SS, 버스가 정류장에서 학교까지 가는 데 걸리는 시간을 TT라고 하자.
    • 1≤S≤1001 \le S \le 100
    • 1≤T≤1001 \le T \le 100

부분문제

  1. (10점) N=1N = 1
  2. (15점) 모든 버스는 XX분 이내로 학교에 도착한다.
  3. (30점) 모든 버스에 대해 T=20T = 20
  4. (45점) 추가 제약 조건 없음

입력 형식

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

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

출력 형식

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

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

예제

예제 1

입력
3 8
2 1
6 3
4 4
출력
4

예제 2

입력
1 30
15 20
출력
-1

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.