프로그램 명: coci_nikola
제한시간: 1 초
본인의 의지와 상관없이, 니콜라는 어느 게임의 주인공이 되어버렸다.
이 게임은 1~N까지 일렬로 번호가 매겨진 N개의 칸 위에서 진행된다.
니콜라는 초기에 1번 칸 안에 있고, 다른 칸들로 점프할 수 있다.
니콜라의 처음 점프는 반드시 2번으로 뛰어야한다.
각각의 점프 결과는 두 가지 경우 중 하나밖에 없음이 보장된다.
- 앞 쪽 방향으로 뛸 경우, 이전 점프의 길이보다 한 칸 더 많이 뛴다.
- 뒤 쪽 방향으로 뛸 경우, 이전 점프의 길이만큼만 뛴다.
예를 들면, 첫번째 점프 이후(2번 칸에 있을 때), 니콜라는 뒤로 1번 칸으로 뛰거나 앞으로 4번 칸으로 뛸 수 있다.
그가 어떤 칸으로 들어갈 때마다, 니콜라는 입장료를 지불해야 한다. 니콜라의 목표는 1번 칸에서 N번 칸으로 "가능한 가장 싸게" 도착하는 것이다.
니콜라가 N번 칸에 도착할 수 있는 가장 싼 비용을 구해주는 프로그램을 작성하여라.
입력
- 첫번째 줄에는 칸의 갯수인 N( 2 <= N <= 1000 )이 주어진다.
- 이후 N개의 줄에는 1~N칸 순서로 각 칸의 입장료가 주어진다. 이 입장료는 500 미만의 양의 정수이다.
출력
N번째 칸에 도달할 때의 가장 작은 비용을 출력한다.
입출력 예제
첫번째 예제를 보면, 2번 칸으로 점프 후에, 1번으로 되돌아간다. 이후 3번 칸과 6번 칸으로 이동하면 된다.
Against his own will, Nikola has become the main character in a game. The game is played on a row of
N squares, numbered 1 to N. Nikola is initially in square 1 and can jump to other squares. Nikola's first
jump must be to square 2. Each subsequent jump must satisfy two constraints:
- If the jump is in the forward direction, it must be one square longer than the preceding jump.
- If the jump is in the backward direction, it must be exactly the same length as the preceding
jump.
For example, after the first jump (when on square 2), Nikola can jump back to square 1 or forwards to
square 4.
Every time he enters a square, Nikola must pay an entry fee. Nikola's goal is to get from square 1 to
square N as cheaply as possible. Write a program that determines the smallest total cost for Nikola to
get to square N.
입력
-
The first line contains the integer N, 2 ≤ N ≤ 1000, the number of squares.
-
Each of the following N lines contains the entry fee for one square, a positive integer less than 500.
The entry fees will be given in order for squares 1 to N.
출력
Output the smallest total cost for Nikola to get to square N.
입출력 예
input
6
1
2
3
4
5
6
output
12
input
8
2
3
4
3
1
6
1
4
output
14
In the first example, after jumping to square 2, Nikola jumps back to square 1. From there he can jump to square 3 and then to 6.
출처:2007-2008/regional
번역:Fate
[질/답]
[제출 현황]
[푼 후(0)]