크리스마스 선물 위의 리본

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

요약

리본 구간마다 목표 진하기가 주어질 때, 연속된 구간을 한 번에 덧염색하되 더 진한 색으로만 바꿀 수 있는 최소 염색 횟수를 구합니다.

난이도: 보통10점 중 5점
유형: 분할 정복, 재귀, 배열
정답자: 아직 제출이 없습니다

문제

크리스마스 선물 상자를 장식할 리본을 준비하고 있다. 리본은 처음에 흰색이며, 이를 염색해서 서로 다른 진하기의 빨간색 줄무늬 무늬를 만들려고 한다. 리본은 여러 구간으로 이루어져 있고, 각 구간은 계획대로 염색해야 한다.

염색 단계를 가능한 한 적게 하여 리본을 완성하려고 한다. 연속된 구간은 같은 빨간색으로 한 번의 단계에 염색할 수 있다. 이미 어떤 빨간색으로 염색된 구간은 더 진한 염료로 덧염색할 수 있으며, 그 구간은 더 진한 색이 된다. 더 연한 색으로 덧염색하는 것은 허용되지 않는다. 리본은 처음에 흰색이므로 모든 구간은 최소 한 번 염색해야 한다.

그림 A.1은 첫 번째 예시의 무늬를 나타낸다. 리본은 여섯 개의 구간으로 되어 있고, 숫자는 계획된 농도 단계를 뜻한다. 숫자가 클수록 진한 색이다. 이 무늬는 세 번의 염색 단계로 만들 수 있다.

리본 전체를 농도 50의 빨간 염료로 염색한다.
왼쪽에서 두 번째 구간을 농도 100의 더 진한 염료로 염색한다.
다섯 번째 구간을 농도 100의 염료로 염색한다.

계획된 줄무늬 무늬를 만드는 데 필요한 최소 염색 단계 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 리본의 구간 수 $n$ ( $1 \le n \le 100$ )이 주어진다.

둘째 줄에는 $n$ 개의 정수 $d_1, d_2, \dots, d_n$ 이 주어진다. $d_i$ 는 $i$ 번째 구간의 계획된 농도 단계이며, 1 이상 100 이하이다. 값이 클수록 진한 색을 뜻한다.

출력

계획된 줄무늬 무늬를 만드는 데 필요한 최소 염색 단계 수를 한 줄에 출력한다.

예제5

예제 1
입력
```
6
50 100 50 50 100 50
```
예상 출력
```
3
```
예제 2
입력
```
5
1 2 3 2 1
```
예상 출력
```
3
```
예제 3
입력
```
5
3 2 1 2 3
```
예상 출력
```
5
```
예제 4
입력
```
10
1 20 100 1 20 20 100 100 20 20
```
예상 출력
```
5
```
예제 5
입력
```
5
10 60 100 30 10
```
예상 출력
```
4
```