[백준] [DP] 계단오르기 2579 (파이썬)

문제설명

• dp 테이블을 무엇으로 설정할지 정하여 점화식을 구하는 것이 관건인데 스스로 풀지 못하였다.
• 잘못접근 한뒤로 구글링 해서 올바르게 접근하였다.

스케치

잘못 접근한 사례

올바르게 접근

코드

# 계단오르기

import sys

n = int(sys.stdin.readline().rstrip())

score = [0] # 0 층 점수 0을 넣어주기
for _ in range(n):
    score.append(int(sys.stdin.readline().rstrip())) # 1층부터 ~ N층까지 점수 넣어주기

dp = [0 for _ in range(n+1)] # 값이 0인 dp 테이블 초기화

dp[0] = score[0]
dp[1] = score[1]

if n >= 2:  #index 오류 안되게 조건 추가
    dp[2] = max(score[2] + dp[0] , score[2] + score[1]) 
    if n>= 3:
        # 점화식 시작 
        for i in range(3,n+1):
            dp[i] = max(score[i] + dp[i-2] , score[i] + score[i-1] + dp[i-3])

print(dp[n])