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

초고

import sys
n = int(sys.stdin.readline().strip())

stair =[]
stair.append(0)
ans = [0]*(n+1)
cnt = 0
for i in range(n):
    stair.append(int(sys.stdin.readline().strip()))

ans[1]= stair[1]
for i in range(2,n+1):
    if cnt <2:
        if ((ans[i-1]+stair[i]) - (ans[i-2]+stair[i])) >= 0:
            cnt+=2
        else:
            cnt =0
        ans[i] = max(ans[i-1]+stair[i], ans[i-2]+stair[i])
    else:
        ans[i] = ans[i-2]+stair[i]
        cnt=0
print(ans[n])

• 3번 연속으로 못올라간다에 초점을 두고 cnt 를 명시적으로 사용하려고함.
• dp 로 푸는 문제임을 눈치챘지만, 정확하게 사용하지 못함.

개선된 코드

import sys
n = int(sys.stdin.readline().strip())
stair = [0]
for _ in range(n):
    stair.append(int(sys.stdin.readline().strip()))

ans= [0] *(n+1)
ans[1] = stair[1]
if n>1:
    ans[2] = stair[1] + stair[2]
for i in range(3,n+1):
    ans[i] = max(ans[i-2], ans[i-3]+ans[i-1])+stair[i] 

print(ans[n])

• 작은 문제에서 부터 큰문제로.
• cnt를 사용하지 않고 암묵적으로 룰이 코드에 들어가게

dp[i - 3] + dp[i - 1] 이 아니라 왜 dp[i - 3] + stairs[i - 1] 일까?

• 한큐에 일어나는 과정인데 dp[i - 3] + dp[i - 1] 최대 점수의 최대 점수 받고 하는건 맞지않음.
• dp[i - 3]과 stairs[i - 1]을 추가하면 (i-3)번째 계단까지 도달한 최대 점수를 고려한 다음 (i-1)번째 계단을 밟음.