[알고리즘] 백준#2294. 동전 2 (dynamic programming)

dp 기본 중 기본!

최소 개수로 n개의 동전 중 k를 만드는 방법이 있다면, 그 개수를 출력하는 문제

문제 풀기

핵심 idea🕶

• 최소이므로 조건에서 최대로 가질 수 있는 값으로 초기 dp 리스트 설정
• dp 리스트에 각 인덱스(k)에 대응되는 값은, k를 만들 수 있는 최소 개수를 의미
• 예를 들어 12라는 수를 만들고 싶다면, dp[12]에 최소 동전개수가 매핑됨
• 해당 동전을 뺐을 때 최소 가짓수 와 현재 최소 가짓수 중에서 더 작은 값을 기록해나가는 알고리즘

code

import sys
inp = sys.stdin.readline
n, k = map(int, inp().split())
coins = [int(inp()) for _ in range(n)]
# print(n,k, coins)
#dp[k] = k원을 만드는데 필요한 최소 동전의 개수
dp = [10001] * (k+1)
dp[0] = 0
for coin in coins:
    for i in range(coin, k+1):
        dp[i] = min(dp[i],dp[i-coin]+1)

if dp[k]==10001:
    print(-1)
else:
    print(dp[k])

회고

• 최솟값을 구하려면 맨 처음에는 최대 값을 골라서 설정해주고 비교해나가면서 설정해주는 방식이 좋다.
• dp 리스트를 정의할 때 index 값에 매핑되는 그 값부터 제대로 정의하는게 핵심이다. 그러고 나면 문제의 실마리가 보인다.