BOJ 백준 2579번, 계단 오르기

BOJ 백준 2579번, 계단 오르기 - Python 파이썬

지안22 2023. 3. 28. 21:40

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

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

# 실패
# 1. 점화식 수정
# 2. 작은 수를 넣었을 때 dp와 stairs 생성이 불가, 런타임 에러가 나서 수정

n = int(input())
dp = [0] * n
# stairs = []
# for i in range(0, n):
#     stairs.append(int(input()))
stairs = [int(input()) for _ in range(n)]

if n <= 2:
    print(sum(stairs))
else:
    dp[0] = stairs[0]
    dp[1] = stairs[1] + stairs[0]
    for i in range(2, n):
        # dp[i] = stairs[i] + max(dp[i - 1], dp[i - 2])
        dp[i] = stairs[i] + max((dp[i-3] + stairs[i-1]), dp[i-2])
    print(dp[-1])