🟩 [백준] [Python] Class3_2579번_계단 오르기

문제

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

2579번: 계단 오르기

풀이

# 백준 2579번 문제 - 계단 오르기
import sys
n = int(sys.stdin.readline())
stair = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    stair[i] = int(sys.stdin.readline())
dp[0] = stair[0]
dp[1] = stair[0] + stair[1]
dp[2] = max(stair[1] + stair[2], stair[0] + stair[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i])
print(dp[n - 1])

이번 문제는 DP를 사용하여 푸는 문제였다. 

처음에 점화식을 구할 생각을 하지 못하고 여러가지 경우의 수를 따지려고 했으나 너무 많은 예외가 있기 때문에 점화식을 구해보았다. 

문제에 나와있는 규칙을 만족하기 위해 

dp[0], dp[1], dp[2] 까지는 하드코딩을 통해 선언해주고

그 뒤의 경우는 모두 점화식을 사용하도록 한다.