동전 교환(거스름돈) 알고리즘

최소 갯수로 동전 교환하는 방법

전체 금액보다 작은 동전중에서
가장 큰 동전부터 차례차례 채워 나간다.

 

 

현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드므로
그 전의 거스름돈에 1을 더하면 된다.

dp[j] = min(dp[j],dp[j-coin[i]]+1);

 

이미 구해진 거스름돈이 더 적은 값을 가지고 있다면 현재의 값을 유지하면 된다.

 

for i <- 1 to M //M=동전 종류 갯수
	dp[i] <- INF

for i <- 0 to N-1 // N=총 가격
  for j <- coin[i] to M
    dp[j] = min(dp[j] ,dp[j-coin[i]] + 1)