💡 지금까지 생각해낸 풀이

• 0부터 i번째 계단까지 올랐을 때, 수의 합의 최댓값을 구하면 된다.

그 방법으로는

필수 : i번째 계단은 반드시 올랐다고 할 경우

1. i-1번째 계단을 오르지 않았을 때

: 0부터 i-2번째 계단까지 올랐을 때의 최댓값 + i번째 계단의 값

   i-3   i-2   i-1    i
    ?  -  O  -  X  -  O

2. i-1번째 계단을 올랐을 때

: 0부터 i-3번째 계단까지 올랐을 때의 최댓값 i-1번째 계단의 값 + i번째 계단의 값

    i-3   i-2   i-1    i
     O  -  X  -  O  -  O   

이 문제는 'i번째 계단을 무조건 지난다고 가정할 때'를 작은 문제로 수행하도록 하였다.
이를 반복적으로 수행하면 (0부터 시작했을 때) N-1번째 계단을 무조건 지나면서 문제를 풀 수 있다.

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

• dp[2] = max(dp[0]+arr[2], dp[1]) 가 아닌 이유 : dp[i] : i번째 계단을 모두 지났을 경우를 고려하는 거니까!!!

💥 에러 발생, 해결

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

이렇게 쓰면 N<3일 때 indexError가 발생하므로 if문을 사용해줘야 한다.

👍🏻 정답코드

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    arr.append(int(input()))
    
# dp[i] = arr[0]~arr[i]까지의 합의 최댓값 (i번째 계단을 꼭 포함해야됨)
dp = [0 for i in range(N)]
if N >= 1:
    dp[0] = arr[0]
if N >= 2:
    dp[1] = arr[0]+arr[1]
if N >=3:
    dp[2] = max(arr[0]+arr[2], arr[1]+arr[2])

    for i in range(3, N):
        dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])
print(dp[N-1])