거스름돈 최소 동전 계산기 (그리디·동적계획법)

동전 구성에 따라 다릅니다. 한국 화폐(10·50·100·500원과 지폐)에서는 큰 것부터 주는 것이 언제나 최적이지만, 이는 이 구성이 「정규(canonical)」이기 때문이지 그리디가 원래 옳아서가 아닙니다. 예를 들어 1·4·6원짜리만 있을 때 8원을 거슬러 주면 그리디는 6+1+1로 3개를 쓰지만 4+4로 2개면 됩니다.

0원부터 차례로 「그 금액을 만드는 최소 동전 개수」를 채워 올라갑니다. 금액 x의 답은 동전 c를 하나 뺀 dp[x−c]에 1을 더한 값들 가운데 가장 작은 것입니다. 앞칸이 모두 최적이면 이 칸도 최적이므로 그리디처럼 앞만 보고 후회하는 일이 없습니다. 계산량은 금액 × 동전 종류 수에 비례합니다.

있습니다. 5원과 6원짜리만으로 10원을 만들 때 그리디는 6원을 먼저 집어 4원이 남아 실패하지만, 5+5로는 만들 수 있습니다. 큰 것부터 집으면 나중에 쓸 수 없는 자투리가 남을 수 있기 때문입니다. 물론 3원과 5원으로 7원처럼 어느 방법으로도 못 만드는 금액도 있습니다.

거스름돈에서 2+1과 1+2는 같은 조합이기 때문입니다. 순서를 따로 세면 1·2·5원으로 5원을 만드는 방법이 9가지가 되지만, 조합으로 세면 4가지입니다. 계산할 때 바깥 반복을 동전으로 두면 조합이, 금액으로 두면 순서를 따지는 수가 나옵니다. 이 계산기는 둘 다 보여 줍니다.

이 계산기가 400원까지 모든 금액을 훑어 그리디와 최적이 어긋나는 가장 작은 금액을 찾아 알려 줍니다. 어긋나는 금액이 없으면 그 구성은 적어도 그 범위에서 안전합니다. 정확한 판정은 파스칼-그로스의 정리로 동전 두 개씩만 봐도 되지만, 화면에서는 실제 반례 금액을 보여 주는 편이 뜻이 분명합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.