[백준2579] / 계단 오르기 - DP

 

백준2579

 

 

 

푼 날짜 : 2024.07.25

푼 문제 : [2579] / 계단오르기

사용한 언어 : python

 

 

점화식:

dp[i] = max(dp[i-2], dp[i-3]+score[i-1])+score[i]

 

dp - 이전 계산 값을 담는 dp 배열

score - 계단점수를 담은 배열

 

푼 방법 : DP

처음에 초기값을 잘못 설정해서 한참을 헤맸다

 

 

이해하기 위해 쉽게 그림을 그려보면, 

 

(내)이해를 돕기위한 그림

 

i는 현재 값

계단을 3연속 밟지 않으면서, 현재 값을 만들기 위해서는 

3전칸+1전칸에 더하거나, 2전칸에 더하는 경우가 만들어진다.

 

dp는 초기값을 잘 설정하는게 중요한데, 초기값 설정은 아래 코드에서 확인할 수 있다.

 

 

 

코드 :

import sys

N = int(sys.stdin.readline())
score = []

for _ in range(N):
    num = int(sys.stdin.readline())
    score.append(num)

if N > 3:
    dp = [0 for _ in range(300+1)]
    dp[0] = score[0]
    dp[1] = score[0] + score[1]
    dp[2] = max(score[0]+score[2], score[1]+score[2])

    for i in range(3, N):
        dp[i] = max(dp[i-2], dp[i-3]+score[i-1])+score[i]
    print(dp[N-1])
    
elif N == 3:
    print(max(score[0]+score[2], score[1]+score[2]))
    
else:
    print(sum(score))

 

 

DP는 항상 직접 작성해보고 머리로 계산을 잘 해보자!