문제

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 
   다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 
밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 
구하는 프로그램을 작성하시오.


<예제>
6				75
10
20
15
25
10
20

풀이

1. 계단의 점수와 최대값을 저장할 리스트를 만든다. s, dp
2. 직전칸에서 계단을 오르는 것과, 한칸 전칸에서 계단을 오르는 것 중 큰 값을 선택해 dp에 저장

import sys

N = int(sys.stdin.readline())
s = [0 for _ in range(N + 3)]
dp = [0 for _ in range(N + 3)]  # 최대값이 저장될 리스트

for i in range(N):
    M = int(sys.stdin.readline())
    s[i] = M

dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])

for i in range(3, N):
    dp[i] = max(dp[i-3] + s[i-1] + s[i], dp[i-2] + s[i])
						# 직전 칸			 한칸 전칸	
print(dp[N-1])

• s, dp를 range(N)로 했을 때 런타임에러(Indexerror)가 났다.
• N = 1일때, dp[2]가 정의되지 않아 에러가 났던 것 같다.
  -> range를 N+3 으로 늘려 줌.