🥇 2294번: 동전 2

👉🏻 2294번: 동전 2

n, k = map(int, input().split())
money = [int(input()) for _ in range(n)]
dp = [float('inf')] * (k+1)
dp[0] = 0

for i in range(1, k+1):
    for coin in money:
        if i - coin >= 0:
            dp[i] = min(dp[i], dp[i-coin] + 1)

print(-1 if dp[k] == float('inf') else dp[k])

 

🤔 왜 이렇게 풀었을까?

• 전형적인 DP 문제입니다. 사실 처음에는 아래처럼 '거스름돈 문제다!!' 생각해서 냅다 그리디로 풀어봤는데, 당연하게도 시간이 초과했습니다.

n, k = map(int, input().split())
money = sorted([int(input()) for _ in range(n)], reverse=True)
min_cnt = float('inf')

for i in range(n):
    cnt, temp = 0, k
    while temp:
        for j in range(i, n):
            cnt += temp // money[j]
            temp = temp % money[j]
        min_cnt = min(min_cnt, cnt)

print(min_cnt)

• 위처럼 그리디하게도 접근할 수 있는 문제이지만, 거슬러줄 동전의 단위에 초점을 맞추기보다는 바텀업 방식으로 1원부터 목표 금액까지의 모든 금액에 대한 최소 동전 개수를 구해 나가는 관점으로도 풀 수 있었습니다.
• 궁극적으로 구하고 싶은 것은 금액 i를 만드는 데 필요한 동전의 최소 개수이고, 이 개수들이 dp 배열에 저장됩니다.
• 만약 coin이라는 동전 하나를 쓰기로 했다면, 그 순간 돈 i 중에서 coin만큼 미리 사용했다고 볼 수 있습니다.
• 그렇기에 코드를 살펴보시면, dp 배열을 갱신하는 식에서 i - coin이라는 값이 들어가게 되는 것입니다!