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

2579번 문제
DP문제이다.
문제를 간략히 이해해보면, 세 계단을 연속으로는 밟을 수 없고(=두 계단을 연속으로 밟으면 한 계단 건너뛰어야한다.), 마지막 계단은 꼭 밟아야 한다.
이번 문제의 힌트는 마지막 계단은 꼭 밟아야한다는 조건에서 알 수 있다.

마지막 계단의 입장에서 이전 계단들이 어떻게 밟힐지를 생각해보면 쉽게 풀 수 있다.

1,2,3,4,5,6 번 계단이 있다고 가정하고, 마지막 계단의 전 계단을 밟을 때와 밟지 않을 때 두가지로 나눠서 생각해보자.

1. 마지막 계단의 전 계단을 밟은 경우
   세 계단 연속으로 밟을 수 없으므로 마지막 계단, 그 전 계단을 밟으면 끝이다.
   즉, 5,6번 계단을 밟는 것이다.
2. 마지막 계단의 전 계단을 밟지 않은 경우
   마지막 계단을 밟고, 전 계단은 안밟으니 전전계단과 전전전계단은 밟을 수 있는 것이다.
   즉, 3,4,6번 계단을 밟는 것이다.

이를 점화식으로 표현해보면 아래와 같이 표현할 수 있다.

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

이것을 코드로 표현해보겠다.
참고로 위의 점화식을 보면, 최소 표본이 3개는 있어야하므로 3개의 표본까지는 하드코딩으로 작성한다.

n=int(input())
stairs=[]
for _ in range(n):
    stairs.append(int(input()))

dp=[0]*n

if n==1:
    print(stairs[0])
elif n==2:
    print(stairs[0]+stairs[1])
elif n==3:
    print(max(stairs[1]+stairs[2], stairs[0]+stairs[2]))
else:
    dp[0]=stairs[0]
    dp[1]=stairs[0]+stairs[1]
    dp[2]=max(stairs[0]+stairs[2], stairs[1]+stairs[2])
    for i in range(3, n):
        dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i], dp[i-2]+stairs[i])
    print(dp[n-1])

이번 문제와 같이 특정 표본에서 연속제한과 같은 제약을 주는 방식은 DP에서 자주 사용되는 방식이므로 까먹지 말고 기억하도록 하자.(참고로 '2156 포도주 시식' 문제도 같은 부류의 문제이니 꼭 풀어보도록 하자.)