[백준] 2579번: 계단 오르기 문제 풀이 파이썬

문제 링크

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

풀이 방식

해당 문제를 읽자마자 DP 문제인 것을 알았고 마지막 계단에 도착했을 때, 두가지 경우의 수를 생각했다.

1. i번째 계단과 i-1번째 계단이 연속될 경우
2. 연속되지 않게 i번째 계단에 도착할 경우

1번 같은 경우에는 i-3번째 계단까지의 최대 합과 더하고, 2번 같은 경우 i-2번째 계단까지의 최대 합과 더한다.
점화식은 다음과 같다.

점화식
1. dp[i] = dp[i-3] + point[i-1] + point[i]
2. dp[i] = dp[i-2] + point[i]

합쳐보면
dp[i] = max(dp[i-3]+point[i-1]+point[i], dp[i-2]+point[i])가 된다.

전체 코드

N = int(input())
# dp에 사용할 배열과 각 계단에 저장할 값을 선언
dp = [0] * (N+1)
point = [0] * (N+1)
for i in range(1, N+1):
    point[i] = int(input())
if N==1:
    print(point[1])
    exit()
elif N==2:
    print(sum(point[:3]))
    exit()
dp[1] = point[1]
dp[2] = point[1]+point[2]
for i in range(3, N+1):
    dp[i] = max(dp[i-2]+point[i], dp[i-3]+point[i-1]+point[i])

print(dp[-1])