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

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
d = [0] * (n)

if len(a) <= 2:
    print(sum(a))
else:
    d[0] = a[0]
    d[1] = a[0] + a[1]
    for i in range(2, n):
        d[i] = max(d[i-3]+a[i-1]+a[i], d[i-2]+a[i])
    print(d[-1])

 

계단의 값을 더해 최댓값을 만들어야 하기 때문에 DP로 풀었다

계단이 2개 이하일 때는 그냥 다 더하면 되기 때문에 if문으로 빼주었고

계단이 3개 이상일 때 첫번째, 두 번째 계단은 수동으로 계산을 해주고 3번째 계단부터 점화식을 이용해 최댓값을 구해주었다

d[i-3]+a[i-1]+a[i] : i-3까지의 계단값 합의 최댓값과 i-1, i 계단의 합

d[i-2]+a[i] : i-2까지의 계단값 합의 최댓값과 i 계단의 합

3번째 계단부터 2계단을 연달아 걸었을 때 / 1계단 건너뛰었을 때