COCI 2015/2016 contest1 3- 풍선 터트리기(BALONI) > 문제은행 : 정보올림피아드&알고리즘




2978 : 풍선 터트리기(BALONI)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
3 회   

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 

수완이는 화살 가지고 사냥 연습하는 것을 좋아한다. 수환이는 임의의 높이에서 화살을 왼쪽에서 오른쪽으로 쏜다. 

화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 

화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 

화살은 계속해서 진행해 가는데 높이는 1 줄어든다. 

따라서 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

 

수완이는 모든 풍선을 터트리되 가능한 적은 수의 화살을 사용하고자 한다. 

수완이를 도와 가장 적은 수의 화살 개수를 구해보자. 


입력형식

첫 번째 줄에는 풍선의 개수 정수 N(1 ≤ N ≤ 1,000,000)이 입력된다. 두 번째 줄에는 각 풍선의 높이 Hi가 공백으로 구분하여 입력된다. 각각의 Hi(1 ≤ Hi ≤ 1,000,000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력형식

첫 행에 필요한 화살 개수의 최소값을 출력한다.

입력 예

5
2 1 5 4 3

출력 예

2

입력 예

5
1 2 3 4 5

출력 예

5

입력 예

5
4 5 2 1 4

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP