동전 거스름돈 문제 (Coin Change Problem) 정해진 동전 d1, d2, …, dk, 거스름돈 n원 단, d1 > d2 > … > dk = 1 부분 문제 w원을 거슬러 줄 때 i번째 동전을 1개 추가할 때 동전 개수 w-di 원을 거슬러 줄 때 필요한 최소 동전의 개수 + 1개 1원씩 증가시켜서 문제 해결 C[j] = min1≤i≤k { C[j - di] + 1 }, if j ≥ di Pseudo code DPCoinChange Input 거스름돈 n원 k개의 동전 액면 d1 > d2 > … > k = 1 Output: C[n] 1. for i = 1 to n C[i] = ∞ 2. C[0] = 0 3. for j = 1 to n { // j는 1원부터 증가하는 (임시) 거스름돈 액수이고, j..
Coin change
동전 거스름돈 (Coin Change) 동전 거스름돈의 최소 동전 수를 찾는 문제 단, 동전 액면 500, 100, 50, 10, 1 Idea 남은 액수를 초과하지 않는 조건하에 가장 큰 액면의 동전을 택함 Pseudo code CoinChange(W) Input: 거스름돈 액수 W Output: 거스름돈 액수에 대한 최소 동전 수 1. change = W n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트 2. while ( change ≥ 500 ) change = change-500, n500++ // 500원짜리 동전 수를 1 증가 3. while ( change ≥ 100 ) change = change-100, n1..
