[백준 / #2579] 계단 오르기 (Python)

문제 설명

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

2579번: 계단 오르기

 

---

문제풀이

점화식을 세워 dp로 풀어야겠다는 생각은 바로 들었지만, 점화식을 세우는 것이 까다로웠다.

연속된 세 개의 계단을 모두 밟아서는 안 된다는 조건을 코드로 구현시키기 힘들었다.

 

생각한 방식은 ???

4번째 계단을 가려면 2번 계단에서 2칸을 오르던가, 1번계단에서 3번계단으로 간 뒤 1칸을 오르는 것!!

한칸을 올라가려면 반드시 그 전에 2칸을 올라야 한다는 조건을 찾고 풀었다.

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n - 1])