[백준] 2579 계단오르기 python

www.acmicpc.net/problem/2579

2579번: 계단 오르기

n = int(input())
stair = [0] + [int(input()) for _ in range(n)]

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

오랜만에 백준문제이다.

이번주부터 다시 알고리즘 열심히 풀기위해 실버 3문제부터 건드렸다.

하지만 DP를 할때 어떤 점화식을 만들어야할지 고민을 많이 했다.

우선, 0번째 계단은 아무것도 없는 상태로 두고. 첫번째와 두번째 계단은 초기 값을 정해준다.

이때 초기값은 한칸씩 넘어왔는지, 두칸을 넘어왔는지 확인하진 않고 둘중에 더 큰값으로 설정한다.

세번째 계단부터는 DP로 두칸을 넘어왔는지, 한칸을 넘어왔는지 확인한다.