백준 2579 - 계단 오르기

문제

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

 

 

 

 

풀이

# 백준 / 실버3 / 계단 오르기

n = int(input())

stairs = [0] * 301

for i in range(1,n+1):
    stairs[i] = int(input())
    
dp = [0] * 301

dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

for i in range(4, n+1):
    dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])

print(dp[n])

 

dp로 풀 수 있는 문제이다.

 

점화식을 세우자면 1. 전단계에서 바로 오는 경우  2. 전전단계에서 오는 경우 가 있는데

3번 연속으로 계단을 오를 수 없다는 조건이 있으므로, 전단계에서 오는 경우는 전단계의 전전단계에서 와야한다. (dp[i-3])

 

이 두 과정을 고려한 최대값을 구하면서 dp[i]를 구할 수 있다.