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

문제 기술

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

입력

첫 번째 줄에 양의 정수 n과 k가 주어진다. 다음 줄에 s1, s2, ..., sk를 나타내는 k개의 양의 정수가 주어진다. 세 번째 줄에 가장 아래 계단부터 위로 차례대로 n개의 각 계단을 밟을 때 비용이 양의 정수로 주어진다.

출력

바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합의 최소값을 출력한다. 올라갈 수 있는 방법이 없으면 –1을 출력한다.

입력 예 1

6 3
2 3 5
2 7 2 9 12 3

출력 예 1

5

입력 예 2

11 3
3 7 9
2 2 2 2 2 2 2 2 2 2 2

출력 예 2

-1

나의 코드

def stair(n, k_num, price):
   if 1 <= n <= 10000:
       price.insert(0, 0)  # 혼란을 방지하기 위해 최초 인덱스 값에 0을 추가함
       dp = [10000 for i in range(n + 1)]  # 0부터 n까지 0을 담은 DP배열 (i번째 계단까지 오르는 데 드는 비용의 최소를 나타내는 배열)을 만듦.
       dp[0] = 0
       for i in range(n+1):  # k_num[0]부터 n번째까지의 계단에 대해서..
           for x in k_num:
               if i >= x:
                   dp[i] = min(dp[i], dp[i-x] + price[i])
               else:
                   break
       if dp[n] == 10000:
           return -1
       else:
           return dp[n]

n, k = map(int, input().split())
k_num = list(map(int, input().split()))
price = list(map(int, input().split()))
print(stair(n, k_num, price))

dp 배열이 0으로 초기화 되어있어야 한다는 생각을 버리지 못해서 시간이 오래 걸린 문제이다. dp를 임의의 매우 큰 수로 값을 채운 뒤, i가 x보다 크거나 같은 경우에 항상 dp[i-x] + price[i]의 값이 들어가도록 했다. 그 이후, dp[n]이 초기값인 10000인 경우는, 가짓수가 없다는 뜻이다. 따라서 이 경우에 -1를 리턴한다. 그게 아닌 경우는 dp[n]을 정상적으로 출력하도록 한다.