시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 209 | 73 | 62 | 46.269% |
Nikola는 자신의 의지와는 상관없이 어떤 게임 속의 메인 캐릭터가 되어버렸다! 이 게임은 1부터 N까지의 번호가 쓰인 일렬로 된 N개의 발판 위에서 진행된다. Nikola는 1번 발판 위에서 시작하여 다른 발판 위로 점프하여 이동할 수 있다. 처음 이동할 때는 무조건 2번 발판 위로 움직이게 되어 있으며, 이후의 이동에는 다음과 같은 제약이 따른다.
예를 들어, 첫 번째 점프 이후(2번째 발판 위에 있는 상황), Nikola는 4번 발판으로 뛰어 갈 수 있으며, 반대 방향인 1번 발판으로 뛰어 갈 수 있다.
그가 매번 각 발판 위에 도달 했을 때, 해당 구역의 통행료를 내야만 한다. Nikola는 가능하다면 N번 발판까지 이동하면서 지불해야 하는 통행료를 최소로 만들고 싶어한다.
첫째 줄에는 발판의 개수 N이 2 ≤ N ≤ 1000 인 정수로 주어진다.
둘째 줄부터 N+1번째 줄에는 1번 발판부터 N번 발판까지 순서대로 각 발판 위로 점프하는데 지불해야 하는 통행료가 주어지며, 이들은 모두 500 이하의 양의 정수이다.
Nikola가 N번째 발판에 도달하기 위한 통행료의 최솟값을 첫 번째 줄에 출력한다.
6 1 2 3 4 5 6
12
8 2 3 4 3 1 6 1 4
14