문제

https://www.acmicpc.net/problem/2579

나의 코드 (답안 참조)

"""
1. 아이디어
dp리스트를 따로 만들어서 여기에는 각 계단별로 갈 수 있는 최대의 점수를 기록한다.
근데 마지막에는 특히 조심해서 생각해야 한다. 마지막에서 고려해야 할 것은
① 마지막 계단의 전 계단을 밟지 않은 경우 ② 마지막 계단의 전 계단을 밟은 경우를 따져야 한다.

2. 시간복잡도
O(n)정도 되지 않을까? 정확히 따지면 for 연산은 n이 4이상 일때 n-3회 돌고
max()은 2개의 비용만 따지니깐 2n-6 = O(n) 이렇게 되나..
"""

from sys import stdin
input = stdin.readline

n = int(input())
scores = [0] * (n+2)
dp = [0] * (n+2) # 점수의 누적 합을 저장하는 리스트

for i in range(n):
    scores[i] = int(input())

dp[0] = scores[0] # 첫번째 계단까지의 누적 합
dp[1] = scores[0] + scores[1] # 두번째 계단까지의 누적 합
dp[2] = max(scores[0] + scores[2], scores[1] + scores[2]) # 세번째 계단까지의 누적 합

for i in range(3, n):
    # 마지막 계단의 전 계단을 밟지 않은 경우, 마지막 계단의 전 계단을 밟은 경우 둘중의 최댓값을 저장.
    dp[i] = max(dp[i-2] + scores[i], dp[i-3] + scores[i-1] + scores[i])

print(dp[n-1])
    

느낀점

처음에 dp = [0] * (n+2) 이 부분에서 (n+1)을 했었는데 런타임 에러가 나서 왜 그런지 몰랐는데 질문 게시판을 보니 (n+1)을 하면 n = 1일때 dp[2]가 없어서 dp[2] = max(~~~) 이 부분은 실행될 수 없다는걸 알았다. 꼼꼼함이 필요하다