동전 교환 문제

거스름돈을 주는 계산원은 넘지 않는 가장 큰 동전을 먼저 집고, 그다음 동전을 집습니다. 유로나 달러에서는 이렇게 하면 항상 동전 수가 최소가 됩니다. 하지만 동전을 1, 3, 4로 바꾸면 같은 습관으로는 두 개면 될 6을 세 개로 냅니다. 동적 계획법은 어떤 동전이든 진짜 최솟값을 찾아냅니다.

각 금액을 만드는 최소 동전과 함께 늘어선 금액들, 그 아래에 크기가 다른 세 종류의 동전
각 금액을 만드는 최소 동전과 함께 늘어선 금액들, 그 아래에 크기가 다른 세 종류의 동전

두 가지 질문

동전 교환 문제에는 두 가지가 있습니다. 첫째는 정확한 금액을 만드는 최소 동전 수를 묻는 것으로, 거스름돈 문제라고도 합니다. 둘째는 그 금액을 만드는 서로 다른 동전 조합이 몇 가지인지 묻는 것입니다. 두 경우 모두 각 종류의 동전을 원하는 만큼 쓸 수 있으며, 둘 다 더 작은 금액의 답으로 모든 금액의 답을 쌓아 올려 풉니다.

최소 동전 수, 단계별로

0부터 목표 금액까지 각 금액에 대한 칸을 한 줄로 만듭니다. 금액 0은 동전 0개, 다른 모든 금액은 무한대에서 시작합니다. 금액을 차례로 훑으면서 각 금액마다 그 금액보다 크지 않은 동전 c를 모두 시도합니다. 금액에서 c를 뺀 칸에 동전 하나를 더한 값이 후보입니다. 가장 작은 값을 남깁니다. 각 칸은 이미 확정된 왼쪽 칸에만 의존하므로 한 번 훑으면 줄이 다 채워집니다.

예제

동전 1, 3, 4가 있을 때: 금액 1은 동전 1개, 2는 2개, 3은 1개(3 하나), 4는 1개가 필요합니다. 5에서는 1(4에 1개가 필요하므로 2개), 3(2에 2개가 필요하므로 3개), 4(1에 1개가 필요하므로 2개)를 시도하고, 최선은 2개입니다. 6에서는 1(5에 2개가 필요하므로 3개), 3(3에 1개가 필요하므로 2개), 4(2에 2개가 필요하므로 3개)를 시도하고, 최선은 3 + 3으로 2개입니다. 그리디라면 4 + 1 + 1로 냈을 것입니다.

방법의 수 세기

조합을 세려면 동전을 하나씩 추가합니다. 첫 번째 동전만 있을 때는 각 금액을 한 가지 방법으로 만들 수 있거나 아예 만들 수 없습니다. 새 동전 c가 들어오면, 금액 a를 만드는 방법은 c 없이 만드는 기존 방법에, c를 다시 쓸 수 있는 상태에서 a − c를 만드는 방법을 더한 것입니다. 그런 방법 각각에 c를 하나 더 붙이면 a를 만드는 방법이 되기 때문입니다. 동전 1, 2, 5로 5를 만드는 방법은 4가지입니다: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1.

그리디로 충분할 때

그리디가 항상 최소 동전 수를 주는 동전 체계를 캐노니컬 동전 체계라고 합니다. 대부분의 현대 화폐는 그렇게 설계되어 있으며, 1994년 데이비드 피어슨은 동전 수에 대해 다항식으로만 늘어나는 단계 수로 동전 체계를 검사하는 방법을 제시했습니다. 옛 영국 동전은 캐노니컬하지 않았습니다. 그리디는 48펜스를 하프 크라운, 실링, 6펜스 동전으로 내지만, 플로린 두 개면 충분합니다.

직접 살펴보기

앱을 열고 표 보기로 바꾼 뒤 단계를 누르세요. 최소 동전 수 모드에서 주황색 칸은 계산 중인 금액이고, 파란색 칸은 동전을 쓰고 남은 더 작은 금액입니다. 아래 행에는 마지막 동전이 기록되고, 마지막에 이 행을 따라 동전을 거꾸로 읽어 냅니다. 방법의 수로 바꾸면 동전이 하나씩 추가될 때마다 값이 행마다 늘어나는 모습을 볼 수 있습니다.

자주 묻는 질문

동전 교환 문제는 배낭 문제인가요?

가까운 친척입니다. 최소 동전 수 버전은 무한 배낭 문제로, 각 동전은 액면가를 무게로 하는 물건이고, 배낭은 정확히 채워야 하며, 목표는 물건 수를 최소로 하는 것입니다.

시간 복잡도는 어떻게 되나요?

동전 k종류와 금액 A에 대해 두 버전 모두 O(k·A)입니다. 최소 동전 수의 표는 A + 1칸, 방법의 수의 표는 (k + 1)·(A + 1)칸이지만, 칸을 제자리에서 갱신하면 한 행으로 충분합니다.

왜 동전을 정해진 순서로 세나요?

각 금액이 모든 동전을 시도하면 1 + 2와 2 + 1이 두 가지 방법으로 세어집니다. 동전을 한 행씩 추가하면 조합이 항상 앞선 동전부터 만들어지므로 각 조합을 정확히 한 번만 셉니다.

방법의 수에서도 동전을 거꾸로 읽어 낼 수 있나요?

하나의 답으로는 안 됩니다. 방법이 많기 때문입니다. 최소 동전 수 버전은 각 금액의 마지막 동전을 기록하므로 최선의 조합 하나를 다시 만들기에 충분합니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

동전 교환 해 보기