알고리즘 공략 빵 - 정보올림피아드 2022 초등부

빵 서브태스크

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

1024 MB

4109

1972

1716

52.000%

문제

KOI 빵은 프로그래밍을 공부하는 학생들에게 인기를 끌고 있다. 이 빵은 맛있을 뿐 아니라, 안에 프로그래밍에 큰 도움이 되는 여러 가지 힌트가 담겨 있어서 매우 인기가 높다.

이렇게 인기가 높기 때문에, 사람들은 KOI 빵이 가게에 들어오자마자 바로 모두 사 간다. KOI 빵을 사려면 빵이 오기 전에 가게에 가서 기다리고 있거나, 빵이 오는 순간에 정확히 맞추어 와야 한다.

N개의 가게가 있고, 현재 위치에서 이 가게까지 가는 데 걸리는 시간, 그리고 KOI 빵이 이 가게에 들어올 때까지 남은 시간이 각각 주어진다. 빵이 가게에 도착하는 순간이나 도착하기 전에 가게에 갈 수 있으면 KOI 빵을 살 수 있고, 빵이 도착한 이후에 가게에 가면 이미 늦어서 빵이 없다.

가장 빨리 몇 분 뒤에 KOI 빵을 구할 수 있는지 구하는 프로그램을 작성하시오. KOI 빵을 구할 수 있는 방법이 없을 수도 있다.

입력

첫 번째 줄에 가게의 수 N이 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐, 한 줄에 하나씩 현재 위치에서 가게까지 가는 데 걸리는 시간 A와, 현재 시점에서 빵이 들어올 때까지 시간 B가 공백을 사이에 두고 주어진다.

출력

KOI 빵을 살 수 없다면, -1을 출력한다.

KOI 빵을 살 수 있다면, 현재 시점에서 빵을 구하는 데 걸리는 최소 시간을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1 ≤ N ≤ 100
• 각 가게에 대해, 현재 위치에서 이 가게까지 가는 데 걸리는 시간을 A, 이 가게에 KOI 빵이 들어올 때까지 남은 시간을 B라고 하자.
  • 0 ≤ A ≤ 1000
  • 0 ≤ B ≤ 1000

서브태스크

번호배점제한

1	19	N = 1.
2	18	모든 가게에 대해 A = 0.
3	17	모든 가게에 대해 B = 10.
4	16	모든 가게에 대해 A > B.
5	15	모든 가게에 대해 A ≤ B.
6	15	추가 제약 조건 없음.

예제 입력 1 복사

3
10 20
15 18
20 15

예제 출력 1 복사

18

예제 입력 2 복사

3
15 13
17 14
20 15

예제 출력 2 복사

-1

출처

Olympiad > 한국정보올림피아드 > KOI 2022 1차대회 > 초등부 1번

 

해설 

 

bread.pdf (koi.or.kr)

 

 

정답

#include <stdio.h>

#define maxn 100
#define inf 1000000000
int N, a[maxn], b[maxn];

int main() {
scanf("%d", &N);

for (int i=0; i<N; i++) {
scanf("%d%d", a+i, b+i);
}

int ans = 1e9;
for (int i=0; i<N; i++) if (a[i] <= b[i]) {
if (b[i] < ans) {
ans = b[i];
}
}

if (ans == inf) printf("-1\n");
else printf("%d\n", ans);
}