동전 거스름돈

동전 거스름돈 문제 (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..