징검다리 건너기 - 구름LEVEL
징검다리 건너기
Quiz Info
징검다리 건너기
100points
Participant
147
Solved Rate
63.2%
15
13


용민이는 A마을에 방문할 일이 생겨 길을 걷던 도중 개울과 N개의 돌로 이루어진 징검다리를 마주하게 됩니다. 그냥 아무 생각없이 건너려고 하던 용민이는 돌들에 묻어있는 무언가를 보고 멈춰섰습니다. 자세히 살펴본 결과, 돌에 독극물이 묻어있는 것을 알게 되었습니다! 따라서 용민이는 최대한 독극물이 묻은 돌을 피해가며 징검다리를 건너려 합니다. 용민이는 돌들을 유심히 관찰하여 각 돌에 묻어있는 독극물의 양을 알아냈습니다. 또한, 돌들의 간격은 일정하여 용민이의 점프력으로 최대 3칸까지 건너뛸 수 있다는 것을 알고 있습니다.

이러한 상황에서 용민이가 독극물이 최대한 묻지 않도록 건너뛰며 돌을 밟았다고 가정했을 때, 용민이에게 묻는 독극물의 양은 얼마일지 구해주세요. 예를 들어, 돌이 7개 있고 독의 양은 각각 [3, 1, 1, 7, 4, 9, 3]이라고 하면 먼저 3칸을 건너뛰고, 그 후 2칸을 건너뛴 후 다시 3칸을 건너뛰어 개울을 건널 수 있습니다. 따라서 [3, 1, 1, 7, 4, 9, 3]의 상황이므로 용민이에게 묻은 독의 양은 1+4=5가 되고, 이 경우가 최소로 묻는 경우로 출력됩니다.


입력


첫째 줄에 돌의 개수를 의미하는 정수 N이 주어집니다. (단, )

둘째 줄에 각 돌에 묻어있는 독의 양을 의미하는 정수  () 공백으로 구분되어 N개 주어집니다. (단, )


출력


용민이가 최선의 방법으로 건넜을 때 묻게 되는 독의 양을 출력합니다.



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
7
3117493
Output
5
Example 2
Input
10
78910987654
Output
22
Example 3
Input
12
1001000100010010000100100100
Output
100
Example 4
Input
20
2029102832535361611730371039313263437
Output
95
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)