[Python]동적계획법 백준 2579

   문제

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

마지막 계단을 무조건 밟아야 한다는 조건을 이용해보자.

해당계단을 밟을때 최대값은 이전계단을 밟고 이전계단의 전전계단을 밟았을때와 전전계

단을 밝을때 중 하나이다.

import sys
 
n=int(sys.stdin.readline())
steps=[]
max_score=[0 for _ in range(n)]
for i in range(n):
    steps.append(int(sys.stdin.readline()))
 
 
 
def score(n):
    # 첫번째 계단
    max_score[0]=steps[0]
    if n==1:
        return
    # 두번째 계단의 최대값은 두계단 모두밟을때
    max_score[1]=steps[1]+steps[0]
    if n==2:
        return
    # 세번재 계단은 1,3 2,3중 큰거
    max_score[2]=max(steps[0]+steps[2],steps[1]+steps[2])
    if n==3:
        return
    for i in range(3,n):
        #이번계단을 밟고
        #전계단 밝고 전계단의 전전계단을 밟을때
        #전전 계단을 밟을때
        max_score[i]=steps[i]+max(steps[i-1]+max_score[i-3],max_score[i-2])
 
score(n)
print(max_score[n-1])