프로그램 명: wooden_stick
제한시간: 1 초
n 개의 나무 막대기가 있다. 각 나무 막대기의 길이와 무게는 알고 있다. 이
나무 막대기들은 나무 처리 기계에 차례대로 처리된다. 해당 막대기에 대한 처리를
하기 위해 준비시간이 필요하다.
나무처리 기계의 준비시간은 다음을 따른다.
- 첫 나무막대기의 준비시간은 1 분이다.
-
길이 l 과 무게 w 를 처리한 후에 , 길이 l <= l' 과 무게
w <= w' 을 가진 나무 막대기는 준비시간은 없다. 그렇지 않다면 준비시간은 1 분이다.
n 개의 나무 막대기를 처리하는데 필요한 준비시간을 최소 준비시간을 구하는 것이
문제이다. 예를 들어 5 개의 막대기를 가지고 있고 크기와 무게가 (4,9) , (5,2) ,
(2,1) , (3,5) , (1,4) 라면 , (1,4) , (3,5) , (4,9) , (2,1) , (5,2) 순으로
처리한다면 준비시간은 2 분이다. 이 시간이 최소 준비 시간이다.
입력 형식
첫 줄은 막대기의 수(1 <= n <= 5000) 이고 다음 줄은 n 개의
쌍이 입력으로 들어온다. 쌍은 (길이, 무게)식으로 입력되고 길이와 무게는 최대
10000 을 넘지 않는다.
출력 형식
최소 준비시간을 출력한다.
입출력 예
입력
5
4 9 5 2 2 1 3 5 1 4
출력
2
출처:acm taejon
[질/답]
[제출 현황]
[푼 후(2)]