[파이썬]백준 2579번: 계단 오르기

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

2579번: 계단 오르기

---

• 문제풀이

동적계획법을 사용하여 계산해준다.

두가지의 경우로 나눌 수 있다.

 

1경우: 1칸, 2칸, 4칸(두칸 가고 한칸 건너띄기)

2경우: 1칸, 3칸(한칸 가고 한칸 건너띄기)

---

• 코드 1

n = int(input())
stairs = [0] 
dp = [0] * (n + 1)

for _ in range(n):
    stairs.append(int(input()))

dp[1] = stairs[1]
if n >= 2:
    dp[2] = stairs[1] + stairs[2]

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

print(dp[n])

 

---

• 후기

동적계획법은 문제가 어느정도 정형화된 느낌이다.