동전 교환 문제란?
동전 교환(Coin Change)은 정해진 동전 종류들로 목표 금액을 만들 때 필요한 최소 동전 개수를 구하는 문제입니다(각 동전은 여러 번 쓸 수 있음). 거스름돈 계산의 일반화로, 동적 계획법의 입문 문제로 자주 나옵니다.
핵심 한 줄: "금액 a의 답은 그보다 작은 금액들의 답에서 만들어진다." 작은 금액부터 차곡차곡 채워 올라갑니다.
왜 그리디로는 안 되나?
"가장 큰 동전부터 욕심껏" 고르는 그리디는 동전 체계에 따라 틀립니다.
동전 {1, 3, 4}로 금액 6을 만들면
- •그리디: 4 + 1 + 1 = 3개
- •최적: 3 + 3 = 2개
이렇게 그리디가 깨지는 경우가 있어 모든 가능성을 고려하는 DP가 필요합니다.
상태 정의와 점화식
dp[a] = 금액 a를 만드는 데 필요한 최소 동전 개수.
각 동전 c를 마지막에 한 개 더 쓴다고 보면
dp[a] = min( dp[a - c] + 1 ) (모든 동전 c에 대해, a ≥ c)
기저: dp[0] = 0 (0원은 동전 0개).
동작 원리
1단계. dp[0] = 0, 나머지는 "도달 불가"를 뜻하는 큰 값(∞)으로 둡니다.
2단계. 금액 a를 1부터 목표까지 늘려가며, 각 동전 c에 대해 dp[a-c] + 1이 더 작으면 갱신합니다.
3단계. dp[target]이 답입니다. 여전히 ∞면 그 동전들로는 만들 수 없다는 뜻(-1 반환).
알고노트 시각화는 금액이 커지며 각 칸이 어떤 동전을 더해 채워지는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(금액 × 동전 수) |
| 공간 | O(금액) |
예시로 따라가기
동전 {1, 3, 4}, 목표 6.
- •dp[1]=1, dp[2]=2, dp[3]=1(동전 3)
- •dp[4]=1(동전 4), dp[5]=2(4+1), dp[6]=2(3+3)
dp[6] = 2가 정답입니다.
자주 하는 실수
- •도달 불가 처리: ∞에 1을 더해 비교하면 오버플로/오답이 날 수 있으니 갱신 전에
dp[a-c]가 ∞인지 확인합니다. - •최소 개수 vs 경우의 수 혼동: "만드는 방법의 수"는 점화식이 다릅니다(동전 루프를 바깥에 두어 중복 조합 방지).
- •기저 누락:
dp[0] = 0을 빼먹으면 전부 도달 불가가 됩니다.
알고노트에서 직접 확인하세요
작은 금액부터 표가 채워지고, 각 금액에서 어떤 동전을 더해 최소가 되는지 알고노트에서 단계별로 확인할 수 있습니다.