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

링크

백준 2579 계단오르기

DP문제는 항상 처음에 접근방법이 헷갈린다..

반대로 생각하면 점화식을 금방 구할 수 있다. 즉, 위에서 아래로 내려간다고 생각하는 것이다.

마지막계단은 무조건 밟아야 하므로 이를 이용한다.
이 경우 마지막계단(N)의 직전계단을 밟는 경우와 밟지 않는 경우가 있다.

• 마지막 직전 계단(N-1)을 밟는 경우
  • 그 이전 계단은 밟아선 안됨
  • 2계단 전(N-3)은 밟아야 함
• 마지막 직전 계단(N-1)을 밟지 않는 경우
  • 그 이전 계단(N-2)를 밟아야 함
  • 2계단 전(N-3)은 밟아선 안됨

이 두가지 경우 중 더 큰 경우를 취하면 된다.
즉, dp(N) = max((arr[N] + arr[N - 1] + dp[N - 3]), (arr[N] + dp[N - 2]))
이라는 점화식을 세울수 있다.

나는 문제를 풀면서 두가지 실수를 했다.

조건을 꼼꼼히 읽지 않아 N이 1인경우와 2인경우를 생각하지 못했다.

그래서 N이 1인경우와 2인경우의 조건을 따로 뺐는데도 indexerror가 발생했다.
베이스가 되는 dp[1]과 dp[2]를 if N==1 조건식 위에서 적어 N == 1일 경우 index에러가 났다.

베이스 부분을 N >=3 이상인 경우로 넣어서 풀 수 있었다.

정답 코드

import sys; input = sys.stdin.readline

N = int(input())
arr = [0] + [int(input()) for _ in range(N)]
dp = [0] * (N + 1)


if N == 1:
    print(arr[1])

elif N == 2:
    print(arr[1] + arr[2])

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

    print(dp[N])

알게된 것👨‍💻

• DP는 꾸준히 연습해야할듯..