문제1863--계단 4

1863: 계단 4

[만든사람 : 이민혁, 한진우]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

1 ~ N번 칸까지 계단이 있고, 0번 칸에서 시작하여 N번 칸에 도착하고자 한다. 계단은 한 번에 1칸 혹은 2칸씩 오를 수 있다. 각 칸에는 점수가 쓰여 있고, 해당 칸을 밟으면 칸에 쓰여 있는 값만큼 점수가 오르거나 내려간다. 단, 0번 칸을 제외한 나머지 칸에서 연속된 세 개의 계단을 모두 밟아서는 안된다. 예를 들어, {0번 칸, 1번 칸, 2번 칸}을 밟는 것은 가능하지만, {1번 칸, 2번 칸, 3번 칸}을 밟는 것은 불가능하다. 또한 0번 칸에서 점수는 0점이다. N번 칸에 도착했을 때 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하시오. 

입력 설명

첫 번째 줄에 계단의 칸 수(N)를 입력한다.

두 번째 줄에 N개의 계단에 적힌 점수(inp[i])가 공백으로 구분되어 입력된다.

(단, N, inp[i]는 자연수이며, 1 <= N <= 15, -100 <= inp[i] <= 100의 범위를 갖는다.)

출력 설명

N번 칸에 도착했을 때 얻을 수 있는 최대 점수를 출력한다.

입력 예시 Copy

6
10 20 15 25 10 20

출력 예시 Copy

75

출처/분류