니콜라의 점프
시간 제한1초메모리 제한128 MB
정방향 점프 길이가 매번 1씩 늘어나고 역방향 점프는 마지막 정방향 길이와 같아야 하는 규칙에서 N번 칸까지 가는 최소 비용을 구하는 문제입니다.
문제
니콜라는 일렬로 놓인 N개의 발판 위를 이동한다. 발판은 왼쪽부터 1번부터 N번까지 번호가 붙어 있다.
니콜라는 1번 발판에서 시작하며, 첫 번째 이동은 반드시 2번 발판으로 가는 길이 1의 점프이다. 이후에는 마지막으로 앞으로 점프했던 거리를 기준으로 다음 규칙을 따른다.
- 앞으로 점프할 때는 마지막 앞으로 점프한 거리보다 1칸 더 멀리 뛴다.
- 뒤로 점프할 때는 마지막 앞으로 점프한 거리만큼 뛴다. 뒤로 점프해도 이 기준 거리는 바뀌지 않는다.
니콜라가 어떤 발판에 도착할 때마다 그 발판의 통행료를 낸다. 시작할 때 이미 서 있는 1번 발판의 통행료는 내지 않지만, 나중에 1번 발판으로 돌아오면 그때는 통행료를 내야 한다.
N번 발판에 도착할 때까지 내야 하는 통행료 합의 최솟값을 구하라.
입력
첫째 줄에 발판의 개수 N이 주어진다. (2 <= N <= 1000)
다음 N개의 줄에는 1번 발판부터 N번 발판까지의 통행료가 차례대로 하나씩 주어진다. 각 통행료는 1 이상 500 이하의 정수이다.
출력
N번 발판에 도착할 때까지 내야 하는 통행료 합의 최솟값을 출력한다.