KOISTUDY

Informatica Online Judge

동전줍기 Small [1127 / 0467]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 365 Total Tried : 779

The Champion of this Problem (C++) : gs18019 - ms / 293byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

길동이가 길을 걷고 있는데, 산신령이 나타나 길에 동전을 일렬로 놓으면서 “길동아, 네 마음껏 동전을 주워가라.

그런데 연속해서 3개의 동전을 줍지는 못한다.”고 하였다. 길동이가 가장 많은 금액의 동전을 주울 수 있도록 도와주는 프로그램을 작성하시오.

예를 들어, 길에 일렬로 놓은 동전이 아래와 같다면 길동이는 최대 38원(7+10+10+11)을 주울 수 있다.

Input

첫째 줄은 동전의 갯수가 n이 입력된다.

다음 줄에는 각 동전들이 입력된다.

[입력값의 정의역]
n <= 20 을 만족하는 자연수이다.
각 동전의 값은 1,000 이하의 자연수이다.

Output

출력내용은 가장 많이 주울 수 있는 동전의 총 합계를 출력한다.

IO Example