| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2008 | 384 | 298 | 18.567% |
저택에 살고 있는 마법사는 지하의 도서관에 자주 방문한다. 어느 날, 마법사는 도서관에 있는 책 \(N\)권을 모두 읽기로 했다. 책은 한 번에 한 권씩만 읽을 수 있지만, 책을 읽는 순서는 마음대로 정할 수 있다.
책을 읽기 시작하는 것은 힘들지만, 책을 완독하고 나면 지식의 습득으로 인한 즐거움을 얻을 수 있다. 즐거움 수치는 정수로 표현할 수 있으며, 마법사의 초기 즐거움 수치는 \(0\)이다. 모든 책을 읽을 때까지 마법사는 다음 과정을 반복한다.
마법사가 잠들지 않고 \(N\)권의 책을 모두 완독할 수 있는지 알려주자!
첫째 줄에 도서관에 있는 책의 개수인 \(N\) \((1 \leq N \leq 100\ 000)\) 이 주어진다.
둘째 줄부터 \(N\)개의 줄에는 두 정수 \(a_i, b_i\)가 공백으로 구분되어 주어진다. \((0 \leq a_i, b_i \leq 10^9)\)
이는 번호가 \(i\)인 책을 읽기 위해 \(a_i\)만큼의 즐거움을 소모해야 하고, 완독 시에는 \(b_i\)만큼의 즐거움을 얻는다는 뜻이다.
마법사가 도서관의 모든 책을 완독할 수 있다면 1을, 없다면 0을 출력한다.
3 1 3 0 2 1 1
1
마법사는 다음 순서로 책을 읽으면 된다.
최종 즐거움은 \(4\)이고, 어떤 순간에도 즐거움 수치는 \(0\) 미만으로 떨어지지 않았기 때문에 마법사는 모든 책을 완독할 수 있다.
2 0 3 4 100
0
마법사가 책 \(1\)을 읽으면 즐거움은 \(0 \rightarrow 0 \rightarrow 3\) 으로 변화한다. 이후 책 \(2\)를 읽기 위해 즐거움을 \(4\)만큼 소모하면 즐거움 수치는 \(-1\)이 된다. 이 경우 마법사는 잠들게 되어 모든 책을 완독할 수 없다. 처음에 책 \(2\)를 먼저 읽어도 마법사는 모든 책을 완독할 수 없다.
4 0 2 3 0 2 2 2 3
1
마법사가 책을 \(1, 3, 4, 2\) 순서로 읽으면 모든 책을 완독할 수 있다.
University > 서강대학교 > 청정수컵 > 2023 서강대학교 청정수컵 > 새내기 Round H번
University > 서강대학교 > 청정수컵 > 2023 서강대학교 청정수컵 > Open Contest H번