[Leetcode 아주 상세한 문제풀이] 322. Coin Change - 코드 line별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 322번 문제 Coin change 다.

우선 문제를 살펴보자.

 

리트코드 322번 문제 Coin change 링크

Coin Change - LeetCode

Coin Change - LeetCode

 

 

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0
 
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

 

 

문제 설명

문제를 간략히 살펴보자.

예를 한 가지 들어 이 문제를 설명하면, 800원을 만들기 위해 필요한 가장 적은 수의 동전은 몇개인가를 찾는 것이다. 이 경우 500원 짜리 동전 하나와 300원 짜리 동전 3개, 총 4개의 동전이 필요하다.

이 문제에서는 동전 단위가 배열로 주어지고 총 금액이 주어진다. 배열 안의 동전 단위를 고려해 총 금액을 만들기 위해 필요한 '최소' 동전 개수가 몇개인지 찾는 문제다. 위의 예시 1번에서 보는 것처럼 11을 만들기 위해서는 5짜리 동전 2개와 1짜리 동전 1개를 취하는 것이 최소 동전 개수다. 주어진 동전 단위로 총 금액을 만들 수 없다면 -1을 리턴한다.

이제 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 푸는 방법 중 가장 단순한 방법은

주어진 배열 안 모든 숫자 조합을 만들어 총 금액과 비교해 보는 것이다.

하지만 우리는 좀 더 효율적인 풀이 방법을 찾고자 한다.

이 문제를 효율적으로 푸는 방법은 dynamic programming을 이용하는 것이다.

즉, Depth First Search (DSF) 방법을 이용해 back tracking을 하는 방식이다.

예를 들어 예시 1번에서 보는 것처럼 동전 단위가 [1, 2, 5]이고 총 금액이 11이라고 해보자.

이 경우 동전 단위 1을 이용하여 1부터 11사이의 금액을 만들수 있는 동전의 개수는 다음과 같다.

 

이제 이 상황에서 단위가 1인 동전을 단위가 2인 동전으로 치환한다고 생각해보자.

예를 들어 총 금액 2 를 만들기 위해서는 아래 표에서 보는 것 처럼 (노란색)

단위1 동전 2개 vs. 단위2 동전 1개 상황에서 최소 동전 필요 개수는 1이 된다.

이때 총 금액이 3이 되는 상황을 잘 고려해야 하는데,

총 금액 3을 만들기 위해서는 단위1 동전 3개 혹은 단위 1 동전1개와 단위2 동전 1개가 필요하다.

우리는 이 사실을 직관적으로 알고 있지만 알고리즘 상에서 구현하기 위해서는 다음과 같이 접근해야 한다.

우리가 단위2 동전이 하나 있는 상황에서 총 금액 3이라는 것은

1) 총 금액 3에서 단위 2 동전을 뺀 금액 (=1) 을 만들 수 있는 최소 동전 개수

2) 단위2 동전 1개

위 두 경우의 합이 필요하다.

따라서 아래 표에서 보는 것처럼 (초록색)

총 금액 3은 단위1 동전 3개로 만드는 경우와

총 금액 3에서 단위2 동전을 하나 뺀 금액을 만들 수 있는 동전 개수 + 단위2 동전 1개를 비교하여

더 작은 동전 개수를 선택하면 된다.

 

 

문제 풀이

이제 코드를 한 번 살펴보자.

우선 동전 단위가 담긴 배열과 총 금액을 입력받기 위한 함수를 정의해 준다 (line 1)

그리고 DFS를위한 변수를 우선 infinity로 초기화 해준다.

이때 변수의 0번째 index는 0이다 (금액이 0이면 0 리턴)

그리고 동전 단위 별로 총 금액을 만들수 있는 동전 개수를 찾기 위해 for loop를 돌려준다 (line 5)

그리고 동전 단위부터 총 금액까지 for loop를 돌리는데 (line 6)

앞서 설명한대로 dp 변수에 해당 금액 (=i)을 만들수 있는 최소 동전 개수를 업데이트 해준다.

이때 중요한 것은 이전에 탐색한 동전 단위 (e.g., 1)로 총 금액을 만들 수 있는 최소 동전 개수와

그 금액에서 해당 동전 단위를 하나 빼서 (e.g., 3-2 = 1) 자기 자신을 더했을 때

더 작은 동전 개수를 취하는 것이 중요하다 (line 7)

그리고 dp 변수에 저장된 값 중 총 금액 (=amount)에 해당하는 값을 리턴하면 된다.

 

 

문제 풀이 코드

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
# Test cases
coins1 = [1, 2, 5]
amount1 = 11
print(coinChange(coins1, amount1))  # Output: 3
 
coins2 = [2]
amount2 = 3
print(coinChange(coins2, amount2))  # Output: -1
 
coins3 = [1]
amount3 = 0
print(coinChange(coins3, amount3))  # Output: 0