322.Coin Change
난이도: 중간(Medium)
Link: LeetCode 322 - Coin Change
풀이 날짜: 2025/10/13(못품)
1. 문제 이해
여러 가지 종류의 동전(coins)과 목표 금액(amount)이 주어졌을 때,
가장 적은 수의 동전으로 목표 금액을 만들 수 있는 최소 개수를 구하는 문제다.
예를 들어, 위 예시에서 가능한 조합은 다음과 같다.
- 11 = 5 + 5 + 1 (3개)
- 11 = 2 + 2 + 2 + 2 + 2 + 1 (6개)
→ 따라서, 최소 개수는 3개가 된다.
그리고, 만약 주어진 동전들로는 금액을 만들 수 없다면, -1을 반환한다.
2. 접근 아이디어 및 자료구조
이 문제는 전형적인 Bottom-up DP (Dynamic Programming) 구조를 가진다.
핵심은 “금액 i를 만들기 위한 최소 동전 개수" 를 dp[i]로 정의하는 것이다.
1. 점화식 아이디어
각 동전을 하나씩 살펴보면서, 현재 금액 i를 만들기 위해 필요한 최소 개수를 갱신한다.
dp[i] = Math.min(dp[i], dp[i - coin] + 1);- dp[i - coin] : 해당 동전을 사용하기 전에 필요한 최소 개수
- +1 : 현재 동전 1개를 추가했기 때문
2. 초기값 설정
dp[0] = 0; // 0원을 만드는 데 필요한 동전 수는 0개
dp[i] = Infinity; // 나머지는 아직 만들 수 없으므로 무한대로 초기화
dp[i] = 금액 i를 만들기 위한 최소 동전 개수
즉,
- dp[0] = 0 (0원을 만드는 데는 동전이 0개 필요)
- 그 외는 처음엔 Infinity로 채워두고, 가능한 조합을 돌며 최소값을 갱신하는 방식이다.
3. 풀이 코드
var coinChange = function(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0; // 0원은 동전 0개로 가능. [0, Infinity, Infinity, Infinity, ...]
for (let coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};- 외부 루프 (for coin of coins) - 각 동전 단위를 하나씩 살펴보며 가능한 금액을 업데이트한다.
- 내부 루프 (for i = coin; i <= amount; i++) - 현재 금액 i에서 i - coin을 만들 수 있었다면, 그 값에 동전 1개를 추가해 최소값을 비교한다.
- dp[i - coin] + 1 → “현재 동전 하나를 추가했을 때”의 최소 동전 개수를 의미
예시 시뮬레이션
Input: coins = [1,2,5], amount = 11 인 경우, 초기 상태는 아래와 같다.
dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
0 1 2 3 4 5 6 7 8 9 10 11
1. coin = 1
| i | dp[i - coin] + 1 | dp[i] | 업데이트 후 |
| 1 | dp[0] + 1 = 1 | ∞ | 1 |
| 2 | dp[1] + 1 = 2 | ∞ | 2 |
| 3 | dp[2] + 1 = 3 | ∞ | 3 |
| … | … | … | … |
| 11 | dp[10] + 1 = 11 | ∞ | 11 |
결과:
dp = [0,1,2,3,4,5,6,7,8,9,10,11]
2. coin = 2
| i | dp[i - 2] + 1 | dp[i] | 업데이트 후 |
| 2 | dp[0] + 1 = 1 | 2 | 1 |
| 3 | dp[1] + 1 = 2 | 3 | 2 |
| 4 | dp[2] + 1 = 2 | 4 | 2 |
| 5 | dp[3] + 1 = 3 | 5 | 3 |
| … | … | … | … |
| 11 | dp[9] + 1 = 5 | 11 | 5 |
결과:
dp = [0,1,1,2,2,3,3,4,4,5,5,6]
3. coin = 5
| i | dp[i - 5] + 1 | dp[i] | 업데이트 후 |
| 5 | dp[0] + 1 = 1 | 3 | 1 |
| 6 | dp[1] + 1 = 2 | 3 | 2 |
| 7 | dp[2] + 1 = 2 | 4 | 2 |
| 8 | dp[3] + 1 = 3 | 4 | 3 |
| 9 | dp[4] + 1 = 3 | 5 | 3 |
| 10 | dp[5] + 1 = 2 | 5 | 2 |
| 11 | dp[6] + 1 = 3 | 6 | 3 |
최종 결과:
dp = [0,1,1,2,2,1,2,2,3,3,2,3]정답
dp[11] = 3
즉, 11원을 만드는 데 필요한 최소 동전 개수는 3개 (예: 5 + 5 + 1)
| 구분 | 복잡도 | 설명 |
| 시간 | O(n × amount) | 모든 동전에 대해 금액 1~amount 반복 |
| 공간 | O(amount) | dp 배열 하나만 사용 |
4. 요점 정리
- 핵심: dp[i] = Math.min(dp[i], dp[i - coin] + 1) → 이전 상태(i - coin)를 기반으로 최소 동전 개수 갱신
- 구조: Bottom-up DP (중복 계산 없이 한 번씩만 갱신)
- 시간 복잡도: O(n × amount)
- 공간 복잡도: O(amount)
이긴 한데... 솔직히 이 방법을 생각해내기란 아직 익숙치가 않다. 이를 위해서 아래의 친절한 Chatgpt 의 설명을 참고하도록 하자.
5. 어떻게 이런 DP 방식을 떠올릴 수 있을까?
처음 Coin Change 문제를 보면 대부분 이렇게 생각합니다.
“주어진 동전으로 목표 금액을 어떻게 만들지?”, “가능한 조합을 다 해보면 되지 않을까?”
예를 들어, amount가 11이고, coins가 [1, 2, 5]라면
“5를 쓰면 6이 남고, 다시 5를 쓰면 1이 남고…” 이런 식으로
모든 조합을 재귀적으로 시도해보려 합니다.
하지만 이렇게 하면 같은 금액을 여러 번 계산하게 됩니다.
예를 들어 coinChange(11)을 계산할 때,
coinChange(10)과 coinChange(6)을 여러 번 반복해서 구하게 되죠.
이건 불필요한 중복 계산이 많아지고, 결국 시간 초과로 이어집니다.
이때 떠올릴 수 있는 게 바로 DP(Dynamic Programming)의 핵심 개념입니다.
“큰 문제는 결국 작은 문제들의 조합이다.”
“그럼 작은 문제의 답을 미리 저장해두면 되지 않을까?”
즉, “금액 11”을 만드는 방법은
“금액 10”, “금액 9”, “금액 6” 등을 만드는 방법 위에 동전 하나를 추가하는 것과 같습니다.
이때, 금액 i를 만들 수 있는 최소 동전 개수를 dp[i]라고 정의하면,
아래와 같은 관계가 생깁니다.
dp[i] = dp[i - coin] + 1즉,
현재 금액 i를 만들기 위해 동전 하나(coin)를 쓴다고 하면, 남은 금액 i - coin은 이미 계산되어 있어야 합니다.
그래서 그 결과에 +1을 해주면 되는 거죠.
하지만 동전이 여러 개 있으므로 가능한 모든 동전에 대해 위 계산을 수행하고, 그 중 가장 적은 개수를 선택해야 합니다.
그래서 점화식은 다음과 같이 완성됩니다.
dp[i] = Math.min(dp[i], dp[i - coin] + 1)이 과정을 작은 금액부터 차례대로 진행하면,
큰 금액을 계산할 때 이미 작은 금액들의 결과가 채워져 있으므로 중복 계산 없이 효율적으로 계산할 수 있습니다.
이 방식을 Bottom-up DP라고 합니다.
이 아이디어의 핵심은 단순합니다.
“금액 i를 만드는 방법은, 그보다 작은 금액(i - coin)을 만드는 방법 위에 동전 하나를 추가하는 것이다.”
즉, 우리가 구하려는 문제는 완전히 새로운 게 아니라 이미 구해둔 하위 문제들의 조합일 뿐이라는 점에 착안한 것이죠.
이 사고방식을 이해하게 되면, Coin Change뿐 아니라 Climbing Stairs, House Robber, Word Break 같은 다른 1D DP 문제들도 훨씬 쉽게 접근할 수 있습니다.
요약
- 처음에는 모든 조합을 시도하는 탐색(Brute Force) 방식으로 생각하게 된다.
- 하지만 같은 부분 문제를 계속 반복하므로 비효율적이다.
- 이 중복을 없애기 위해 결과를 기억(Memoization)하거나,
- 작은 값부터 쌓아올리는 Bottom-up DP로 바꾼다.
- 결국, “금액 i를 만들기 위한 최소 동전 개수는 (i - coin)까지의 최소 개수 + 1”로 정의할 수 있다.
- 이 논리를 반복해 dp 배열을 채워나가면 효율적인 풀이가 완성된다.