시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 615 | 102 | 69 | 19.714% |
찬수는 1번에서 N번까지 번호가 매겨진 N권의 책을 가지고 있다. 찬수는 이 책을 꽂을 수 있는 책장을 설계하려고 한다. 찬수가 가지고 있는 i번 책의 두께는 ti이고, 높이는 hi이다. 단, 1 ≤ i ≤ N이다. 이 책들을 번호 순서대로 책장에 꽂아야하고 번호의 순서를 임의로 바꾸어 꽂을 수 없다.
이 책들을 책장의 가장 아래 칸부터 위 칸의 순서로, 같은 칸에서는 왼쪽부터 오른쪽으로 책의 번호 순서로 꽂는다. 한번 위 칸으로 옮겨와서 책을 꽂으면 다시 아래 칸으로 내려가서 책을 꽂을 수 없다. 책장의 칸의 높이는 그 칸에 꽂는 책들 중 가장 높이가 높은 책에 의해 결정되며 책이 꽂혀있는 칸들의 높이의 합이 책장의 높이가 된다. 책장의 폭은 꽂혀있는 책의 두께의 합이 가장 큰 칸에 의해 결정된다. 단, 책장을 구성하는 나무의 두께는 고려하지 않는다.
책을 모두 꽂은 후의 책장 전체의 높이를 H, 책장의 폭을 L이라고 할 때, 찬수는 H와 L중 최댓값을 최소로 하는 책장을 설계하려고 한다.
이 책장의 H와 L중 최댓값을 최소로 하는 책장을 구하는 프로그램을 작성하시오.
입력의 첫 번째 줄에 책의 수를 나타내는 하나의 정수 N이 주어진다. 두 번째 줄부터 N개의 줄에, 책들의 번호 순서대로 한 줄에 한권씩, 각 책에 대한 두께 ti와 높이 hi를 나타내는 두 정수가 하나의 빈칸을 사이에 두고 주어진다.
첫째 줄에 책을 모두 꽂은 후의 책장 전체의 높이와 책장의 폭 중에서 최댓값을 최소로 하는 값을 하나의 정수로 출력한다.
7 8 6 2 3 6 5 4 5 5 7 1 2 5 4
16
9 2 2 7 5 3 8 4 4 7 4 8 7 9 2 6 6 7 9
22
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2011 > 고등부 5번