문제
농부 창호의 소들은 해가 질 때를 좋아한다. 그들은 저 멀리 보이는 도시의 지평선을 볼수 있다.
창호의 소인 베시(소)는 skyline 정보가 주어질 때 얼마나 많은 빌딩이 있는가를 알고자 한다.
빌딩의 개수는 최소로 하여야 한다.
빌딩은 사각형 모양이고 스카이라인은 길이는 1 에서 W (1≤W≤1,000,000) 폭 만큼이고,
지평선의 높이가 변화는 지점의 x 좌표와 y 좌표(1≤x≤W , 0≤y≤500,000 )가 N (1≤N≤50,000 ) 개 주어진다
예를 들어 지평선 모양이 다음과 같다면 지평선의 정보는 (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1) 이다.
위의 스카이라인으로 만들 수 있는 최소 빌딩수는 6 개이다.
입력
첫 줄에는 N , W 가 주어진다. 다음 N 줄에는 x 와 y 점의 좌표가 지평선이 변하는 지점마다 주어진다. x 좌표는 증가하는 순으로 주어지고 입력의 첫 데이터의 x 좌표는 항상 1 이 될 것이다.
<부분문제>
서브태스크 #1(18점):
N<=100 서브태스크 #2(82점):
N<=50,000
출력
주어진 지평선을 만들수 있는 최소 빌딩수를 출력한다.
예제
10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
6
출처
USACO November 2005 Silver
로그인해야 코드를 작성할 수 있어요.