[알고리즘] 계단 오르기 2

문제 기술

n(1이상 10,000이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 1개, 3개 혹은 4개의 계단만 오를 수 있으며, 각 계단은 밟을 때 비용이 있다. 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합이 최소가 되도록 하면서 올라가고자 한다. 이때의 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 양의 정수 n이 주어진다. 다음 줄에 가장 아래 계단부터 위로 차례대로 n개 각 계단을 밟을 때 비용이 양의 정수로 주어진다.

출력

바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합의 최소값을 출력한다.

입력 예

6
2 7 2 9 12 3

출력 예

5

나의 코드

import sys

def stair(n, price):
   if 1 <= n <= 10000:
       price.insert(0, 0) # 0번째 계단에서의 값을 나타내기 위해 임의로 0을 넣음.
       dp = [0 for i in range(n+1)] # 최소값이 들어갈 dp 배열을 전체 0으로 해서 만들음.
       dp[0], dp[1], dp[2], dp[3], dp[4] = price[0], price[1], price[1] + price[2], price[3], price[4] # 4번째까지는 최소값을 직접 구할 수 있으므로, 구해줌.
       for i in range(5, n+1): # 5번째부터 n까지 for문을 돌림.
           dp[i] = min(dp[i-3], dp[i-4], dp[i-1]) + price[i]
        # i-1번째, i-3번째, i-4번째 값 중 최소값에 i번째 계단에 오르는데 필요한 비용을 더해줌.
       return dp[n] n번째 계단을 오르는 데 필요한 비용의 최소값을 리턴.

n = int(sys.stdin.readline())
price = list(map(int, sys.stdin.readline().split()))
print(stair(n, price))

기본적인 동적 계획법 문제에서 일부 사항이 추가된 문제이다.우선 4번째 계단에 오르는 비용까지는 직접 구해줄 수 있다. 그리고, 계산상 필요했기 때문에 0번째 계단의 값을 0으로 넣어줬다.

마지막 계단은 무조건 밟게 되므로 메인 for문 내에서 price[i]를 추가해줬고, 거기에 1, 3, 4번째 계단까지의 비용의 최소값을 더해줬다. 재귀적으로 구한 것이다.

그렇게 어렵진 않았다. 🤔