[백준][dp] 2293. 동전1

2293. 동전1

 

• 내 풀이
  • "방법의 수"를 세는 문제이기 때문에, 동전의 순서가 영향을 미치지 않아 정렬이 필요없음

동전 조합 문제  VS 동전 거스름돈 문제 

1. 동전 조합 문제
특정 금액을 만드는 경우의 수를 구하기
→ 모든 동전을 독립적으로 누적하면 되므로 순서가 중요하지 않음

예: 1, 2, 5원 동전으로 5원을 만드는 방법의 수는?
(1+1+1+1+1) / (1+1+1+2) / (1+2+2) / (5) →총 4가지

- 점화식: dp[i] += dp[i - coin]

2. 동전 거스름돈 문제 
특정 금액을 만드는 최소 동전 개수를 구하기
→ 작은 동전부터 탐색하는 것이 효율적. ( 정렬 필요 )

예: 1, 2, 5원 동전으로 11원을 만드는 최소 방법?
5+5+1=3개

- 점화식: dp[i] = min(dp[i], dp[i - coin] + 1)

n,k=map(int,input().split())
dp=[0 for _ in range(k+1)]
coins=[]
dp[0]=1
for _ in range(n):
    coin=int(input())
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])

---

 

동전 거스름돈 문제와 비교

14916. 거스름돈

 

k = int(input())
coins = [2, 5]
dp = [float('inf') for _ in range(100001)]
dp[0]=0
dp[2]=1
dp[5]=1

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

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