Whitespace

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

요약

각 줄의 공백 개수가 주어지고 RETURN 키가 현재 줄의 공백 수만큼 새 줄을 만들 때, 빈 문서에서 목표 프로그램을 만드는 최소 키 입력 수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Whitespace는 공백과 줄 바꿈만으로 코딩하는 프로그래밍 언어이다. 공백은 SP, 줄 바꿈은 NL로 나타낸다.

영선이에게는 Whitespace로 작성한 프로그램이 있고, 이 프로그램은 길이가 $N$ 인 수열 $L$ 로 나타낼 수 있다. $L_i$ 는 $i$ 번 줄에 있는 SP의 개수이고, 모든 줄은 NL로 끝난다. 즉, 소스 코드는 $L_0$ 개의 SP, NL, $L_1$ 개의 SP, NL, $\ldots$ , $L_{N-1}$ 개의 SP, NL로 이루어져 있다.

오늘 영선이는 효빈이가 만든 에디터로 이 프로그램을 입력하려고 한다. 에디터의 커서는 문서의 처음이나 끝, 또는 인접한 두 문자 사이 어디에나 둘 수 있다. 커서를 옮기는 데에는 키 입력이 필요하지 않다.

에디터에는 다음 3가지 특별한 키가 있다.

SPACE: 현재 커서 위치에 SP를 하나 삽입한다.
DELETE: 커서 바로 오른쪽에 있는 SP를 삭제한다. 오른쪽 문자가 NL이면 사용할 수 없다.
RETURN: NL을 하나 입력한 다음 SP를 $K$ 개 입력한다. $K$ 는 커서가 있는 줄의 SP 개수와 같다. 커서 바로 오른쪽 문자가 NL일 때만 사용할 수 있다. 예를 들어 문서가 SP NL SP SP NL SP SP SP NL일 때 두 번째 NL 앞에서 RETURN을 누르면 문서는 SP NL SP SP NL SP SP NL SP SP SP NL이 된다.

지금 에디터에는 NL 하나만 입력되어 있다. $L$ 이 주어졌을 때, 소스 코드를 완성하는 데 필요한 키 입력 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ 이 주어진다. 둘째 줄에 $L_0, L_1, \ldots, L_{N-1}$ 이 공백으로 구분되어 주어진다.

$1 \le N \le 50$
$0 \le L_i \le 1\,000\,000$

출력

첫째 줄에 소스 코드를 완성하는 데 필요한 키 입력 횟수의 최솟값을 출력한다.

힌트

첫 번째 예제에서는 다음과 같이 6번의 키 입력으로 문서를 완성할 수 있다.

NL
SP NL
SP SP NL
SP SP SP NL
SP SP SP NL SP SP SP NL
SP SP SP NL SP SP SP NL SP SP SP NL
SP SP SP NL SP SP NL SP SP SP NL

예제4

예제 1
입력
```
3
3 2 3
```
예상 출력
```
6
```
예제 2
입력
```
1
0
```
예상 출력
```
0
```
예제 3
입력
```
3
1 2 4
```
예상 출력
```
6
```
예제 4
입력
```
5
250 105 155 205 350
```
예상 출력
```
499
```