[S3] 백준 2579 - 계단 오르기 (Python3)

2579번: 계단 오르기 (acmicpc.net)

2579번: 계단 오르기

---

해결방법

다이나믹 프로그래밍(이하 dp) 문제이므로 점화식을 세워서 해결했다.

풀이👀

$a_n$번째 계단에 오르려면 $a_{n-3}$ > $a_{n-1}$ 순으로 오르거나, $a_{n-2}$에서 바로 오르는 경우가 있다.

두 경우 중에서 더 큰 값을 만드는 경우로 $a_n$을 오르는게 이 문제 풀이의 핵심이다.

dp 문제는 개인적으로 dp table을 활용해 푸는 경우가 쉽게 풀리기 때문에 dp 라는 이름의 list를 만들었다.

dp의 i번째 원소를 $d_i$라고 할때 점화식은

  $$d_i  = a_i + max( a_{i-1} + d_{i-3}, d_{i-2} )$$  

로 세울 수 있다.

*단, $d_1  = a_1$,  $d_2 = a_2 + a_1$,  $d_3 = a_3 + max(a_1 , a_2)$ 이다.

---

코드🐱‍👓

n = int(input())
A = [int(input()) for _ in range(n)]

dp = [0] * n
try:
    dp[0] = A[0]
    dp[1] = A[1] + A[0]
    dp[2] = A[2] + max(A[1], dp[0])
    for i in range(3, n):
        dp[i] = A[i] + max(A[i-1]+dp[i-3], dp[i-2])
except:
    None
print(dp[-1])

코드 설명

n 이 3보다 작은 경우에 제대로 된 동작이 안 된다. 그런데 이런 경우를 따로 잡자니, 코드가 너무 어지러워 보여서 try-catch문으로 간단히 해결해보고자 했다.