백준 2579 - 계단 오르기 (파이썬)

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

전형적인 DP 문제이다..

이 문제의 조건은 다음과 같다.

1. 연속된 3개 계단을 모두 밟으면 안된다.
2. 마지막 도착 계단은 반드시 밟아야한다.
3. 계단은 한번에 한 계단 또는 두 계단씩 오를 수 있다.

위 그림의 예제에서는 6개의 계단이 주어진다.

S = 10, 20, 15, 25, 10, 20

1. 마지막 층인 20은 무조건 밟아햔다. 그럼 10을 밟게 되면 25는 못 밟으니까, 10을 버리고 25를  밟는게 최적
2. 15를 밟게 되면 10, 20을 못밟으니까, 15를 버리고, 10, 20을 밟는게 이득
3. 총 4개를 밟는 것이 최선, 총 75의 값을 가지게 된다.

수열로써 값을 나타내면 다음과 같다.

1. aN은 N번째, 최대 점수 (바로 전 계단을 밟지 않음)
2. bN은 N번째, 최대 점수 (바로 전 계단을 밟음)

즉, 두개의 수열을 가지고 점화식을 생성해야한다. 단 N >= 2

예시를 들면 다음과 같다.

a2 = 20(0 + 20), b2 = 30(10 + 20)
a3 = 25(10 + 15), b3 = 35(0 + 20 + 15)
a4 = 55(10 + 20 + 25), b4 = 50(10 + 15 + 25)
a5 = 15까지 올라오는 b3 + 10 = 45, b5 = b2 + 25 + 10 = 65

이것을 식으로 정리하면 다음과 같다.

aN = Sn + max(aN - 2, bN - 2)
bN = Sn + Sn - 1 + max(aN - 3, bN - 3)

즉 해당 문제를 풀기 위한 코드는 다음과 같다.

N = int(input())
S = [0] * N
for i in range(N) :
    S[i] = int(input())

A = [0] * N
B = [0] * N

A[0] = S[0]
B[0] = S[0]

for i in range(1, N) :
    if i >= 2 :
        A[i] = S[i] + max(A[i - 2], B[i - 2])
    else :
        A[i] = S[i]
    
    if i >= 3 :
        B[i] = S[i] + S[i - 1] + max(A[i - 3], B[i - 3])
    else :
        B[i] = S[i] + S[i - 1]

print(max(A[N - 1], B[N - 1]))