풍선 맞추기

면접 대비

시간 제한2초메모리 제한256 MB

요약

왼쪽부터 풍선을 순서대로 맞추며 맞힐 때마다 한 칸씩 내려가는 화살을 가장 적게 쏩니다.

문제

큰 방 안에 풍선 $N$ 개가 왼쪽에서 오른쪽으로 일렬로 떠 있다. 진솔이는 활 쏘기를 좋아해서 화살을 늘 왼쪽에서 오른쪽으로 쏘고, 쏘는 높이는 마음대로 고른다.

화살은 고른 높이 $H$ 를 그대로 유지한 채 오른쪽으로 날아가다가, 높이가 $H$ 인 풍선을 처음 만나면 그 풍선을 터뜨린다. 터진 풍선은 사라지고, 화살은 높이가 1 낮아진 $H-1$ 에서 계속 오른쪽으로 날아간다.

풍선을 하나도 남기지 않고 모두 터뜨리려고 한다. 필요한 화살의 최소 개수를 구하라.

첫째 줄에 정수 $N$ 이 주어진다.

둘째 줄에 풍선 $N$ 개의 높이 $H_1, H_2, \dots, H_N$ 이 왼쪽에서 오른쪽 순서로 주어진다. $H_i$ 는 왼쪽에서 $i$ 번째 풍선의 높이다.

첫째 줄에 모든 풍선을 터뜨리는 데 필요한 화살의 최소 개수를 출력한다.

첫 번째 예제에서는 화살 하나로 높이 5, 4, 3인 풍선을 차례로 터뜨리고, 다른 화살 하나로 높이 2, 1인 풍선을 터뜨리면 된다. 그래서 화살 2개면 충분하다.