백준(2579) - 계단 오르기 Python

백준(2579) - 계단 오르기

문제풀이: DP, 파이썬

각 위치의 최대값을 기록하는 DP테이블을 만든 후 마지막 계단위치를 출력하면 된다.

1. 첫 번째 계단은 자기 값

2. 두 번째 계단은 첫번째 + 두번째 값

3. 세번째 계단부터는 연달아 3개의 계단을 오를수 없다는 조건이 있기때문에 첫번째 계단값과 두번째 계단값 중 큰 값과 세번째 계단값을 합한 값이 된다.

4. 그 이후 부터는

   dp[i] = max(dp[i-3] + steps[i-1] + steps[i], dp[i-2] + steps[i]) 조건으로 채워 나가면 된다.

계단의 크기가 입력으로 받기때문에 dp 테이블과 계단리스트를 n만큼으로 초기화시키면 컴파일 에러가 날 수 있으니 주의하자.

import sys
input = sys.stdin.readline

n = int(input())
steps = [0] * 300
for i in range(n):
    steps[i] = int(input())

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