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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input().strip()))

# dp -1로 초기화
# dp[x] = x원을 만들기 위해 사용한 동전의 최소 개수
dp = [-1]*(1000001)
dp[0] = 0
for coin in coins:
    # 가치가 같은 동전이 여러 번 주어질 수 있다.
    # 이미 dp[coin] = 1 이라면 그냥 스킵
    if dp[coin] == -1:
        dp[coin] = 1


for i in range(1, k+1):
    if dp[i] != -1:
        continue

    tmp = []
    for coin in coins:
        if i - coin >= 0 and dp[i-coin] != -1:
            tmp.append(dp[coin] + dp[i-coin])

    if len(tmp) <= 0:
        continue
    dp[i] = min(tmp)

print(dp[k])

---

🧂아이디어

DP

• dp[x] = x원을 만들기 위해 사용한 동전의 최소 개수

• dp[0] = 0으로, 입력에서 주어지는 동전들은 dp[coin] = 1로 초기화하고, 나머지는 -1로 초기화한다.

• i - coin >= 0 이고, dp[i-coin] != -1일 때, dp[i] = dp[coin] + dp[i-coin] (1 + dp[i-coin]) 의 최소값

🧐

• 런타임 에러(IndexError):
• 처음에 dp를 [0]*(k+1)로 초기화해서 발생한 에러. 주어지는 동전의 가치는 100,000보다 작거나 같은 자연수이므로 리스트의 크기를 100,000보다 큰 범위로 초기화해주면 해결할 수 있다.