백준 2579 python [계단 오르기]

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

import sys

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()

def input():
    return sys.stdin.readline().strip()

def solvedp():
    if(N == 1):
        print(arr[0])
        return
    if(N == 2):
        print(arr[0] + arr[1])
        return
    if(N == 3):
        print(max(arr[2]+arr[1], arr[2]+arr[0]))
        return

    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    dp[2] = max(arr[2]+arr[1], arr[2]+arr[0])

    for i in range(3, N):
        dp[i] = max(arr[i]+arr[i-1]+dp[i-3], arr[i]+dp[i-2])

    print(dp[N-1])

N = int(input())
arr = [0] * (N+1)
dp = [0] * (N+1)

for i in range(0, N):
    arr[i] = int(input())

solvedp()

---

DP 문제는 점화식을 잘세우는게 중요한데 쉽사리 떠오르지 않았다.

3번 연속 밟으면 안되는 부분 때문에 어떻게 구현해야 할까와

어느 계단에서 dp 배열의 값을 사용해야할까 고민하다가

살짝 점화식 힌트를 얻었다.

max(arr[i]+arr[i-1]+dp[i-3], arr[i]+dp[i-2])

유레카

현재 계단에서 두칸 혹은 세칸 떨어져 있는 값은 dp 배열의 값을 사용한다.

두세칸 떨어져 있는 계단의 값은
현재 계단과 3번 연속 밟는것과는 무관하기 때문에
그 계단에서의 최고 값을 가져오면 된다.

계속 느끼지만 DP 문제는 구현보다 아이디어가 더 어렵다..
아이디어 >>>>> 구현