[Python/BOJ] 백준 2579 계단오르기_DP

 

 

점수를 저장할 score 리스트 , dp값을 저장할 리스트를 만든다. 

 

들어오는 계단의 개수가 1,2,3 일때는 하드코딩을 해준다. 

 

그 이상일 때는 for문을 돌면서 dp 배열을 채워준다. 

조건에는 한 계단 혹은 두 계단씩 오를 수 있다는 조건이 있다. 

그리고 마지막 도착 계단은 반드시 밟아야 한다. 

 

 

마지막 계단을 밟고 2단계 이전 계단을 밟는 경우와

(score[i] + dp[i-2] )

 

마지막 계단과 바로 이전 계단 그리고 2단계 이전 계단을 밟는 경우가 있을 수 있다. 

(score[i] + score[i-1] + dp[i-3])

 

 

 

 

 

 

 

코드 : 

if __name__=="__main__" :
    score = []
    dp = []
    
    l = int(input())
    score.extend(list(int(input()) for _ in range(l)))

    if l == 1 :
        print(score[0])
    elif l == 2 : 
        print(score[0]+score[1])
    elif l ==3 : 
        print(max(score[1]+score[2], score[0]+score[2]))
    else : 
        dp.append(score[0])
        dp.append(score[0]+score[1])
        dp.append(max(score[1]+score[2], score[0]+score[2]))
        for i in range(3,l) :
            dp.append(max(dp[i-2]+score[i], dp[i-3]+score[i-1]+score[i]))
        print(dp[l-1])