문제 번호 3508 --동전줍기

3508: 동전줍기

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 66  해결 문제 수: 31
[제출][채점상황][게시판][:]

문제 설명

길동이가 길을 걷고 있는데, 산신령이 나타나 길에 동전을 일렬로 놓으면서 “길동아, 네 마음껏 동전을 주워가라. 그런데 연속해서 3개의 동전을 줍지는 못한다.”고 하였다. 길동이가 가장 많은 금액의 동전을 주울 수 있도록 도와주는 프로그램을 작성하시오.
예를 들어, 길에 일렬로 놓은 동전이 아래와 같다면 길동이는 최대 38원(7+10+10+11)을 주울 수 있다.

입력

첫째 줄은 동전의 갯수가 입력되고 동전의 수는 100이하의 자연수이다. 다음 줄에는 동전의 값들이 입력된다. 입력된 값들은 자연수이고 합해서 30,000을 초과하지 않는다.

출력

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

입력예시

8
5 7 10 1 2 10 11 6 

출력예시

38

도움말

출처

[제출][채점상황]