[DP 알고리즘] 계단 오르기 S3

기출 : BOJ #2579

 

선택한 계단들에 새로운 계단을 추가할 수 있다 (확장성)

현재 상황을 직전 상황들로 표현할 수 있다 (점화식 작성 가능)

 

D[n][m] = n번째 계단을 선택할 때 연속으로 m개의 계단을 선택한 경우 최댓값

 

D[n][1] = max(D[n-2]) + score[n]

D[n][2] = D[n-1][1] + score[n]

계산할 범위는 3~n까지 이다

 

 

 

# d[n][2] = d[n-1][1] + score[n]
# d[n][1] = max(d[n-2]) + score[n]
# d[1][1] = score[1]
# d[2][1] = score[2]
# d[1][2] = 0
# d[2][2] = score[1] + score[2]

걔
n = int(input())
d = [[0 for _ in range(3)] for __ in range(n+1)]
score = list()
score.append(0)
for _ in range(n):
    score.append(int(input()))

if n>=1:
    d[1][1] = score[1]
    d[1][2] = 0
if n>=2:
    d[2][1] = score[2]
    d[2][2] = score[1] + score[2]
for i in range(3, n+1):
    d[i][1] = max(d[i-2]) + score[i]
    d[i][2] = d[i-1][1] + score[i]

print(max(d[n]))