<2022모각코/TIL> [백준/python] 2579- 계단오르기

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

dp[0] = stair[0]

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

print(dp[n-1])

알고리즘:

1. Stair 배열을 받고, DP배열도 n개로 만듦

2. dp[1]은 2번째 칸이므로 그냥 1번쨰 2번째 두개 더한 것이 최대

3. dp[2] 는 23번째 칸과 13번째 칸의 최대를 구함

4. dp[3]부터는 두가지 로 나눔. 첫번째는 i번째 칸의 전을 밟은 것과, i번째 칸의 전전을 밟은 것. 전을 밟은 것은 전전을 밟을 수 없기때문에 dp[i - 3]을 더해주고, 전전칸을 밟는 것은 그냥 dp[i - 2] 를 해줆.

 

dp를 정확하게 이해할 수 있었던 문제였다.