[리트코드/leetcode/python] 518. Coin Change II

이미지를 누르면 문제 링크를 보실 수 있습니다

많이들 접해보신 DP의 단골문제 동전문제입니다. 주어진 동전을 얼마든지 사용하면서 amount를 만들 수 있는 총 가짓수를 구하는 문제인데요, 이 외에도 가장 최소의 동전 개수만 사용해서 푸는 문제 등 동전에 관한 DP문제는 이제 거의 정형화된 알고리즘으로 자리잡았습니다.

그렇기 때문에, 해당 문제를 푸는 방향도 처음 본 문제라면, 접근이 어려울 수 있습니다. 특히, DP는 많은 유형을 풀어봄으로써 어느정도 유형화를 하는 것도 방법입니다.

 

이 문제에 대해서는 먼저, 메모제이션 기법을 사용해서 전형적인 DP로 풀어보도록 하겠습니다.

그럼, 이 문제에 대해 이해를 시각화해볼까요?

DP

원리를 살펴보면 다음과 같은 테이블을 그릴 수 있습니다.

테이블의 열은 '(원)'을 뜻하며, 0원부터 amount(=5)원까지

테이블의 각 행에 있는 동전리스트에 있는 동전으로 만들 수 있는 방법을 적은 테이블입니다.

 

예시로 [1,2,5] 의 동전리스트가 있다고 해봅시다.

가장먼저, 빈 리스트 [] , 그러니까 아무런 동전을 사용하지 않고 0원을 만드는 방법은 1가지가 있겠죠. 이건 그냥 디폴트입니다.

그리고, 1원부터 amount(=5)원까지 만들 수 있는 방법은 당연히 없습니다. (0가지)

그래서 위의 표에서 1행은 0원을 만들 수 있는 1가지를 제외하고 다른 칸이 0으로 채워진 것입니다.

그렇다면, 어떤 동전리스트의 구성이든, 0원을 만들 수 있는 방법은 몇가지일까요? 이것도 마찬가지로 1가지로 디폴트입니다.

이렇게, 첫 시작은 1행 1열을 제외한 모든 1행은 0으로 채워지겠고, 모든 1열은 1로 채워진채로 본격적으로 탐색이 시작되는 것입니다.

 

테이블에 동전을 작은 단위부터 추가해보면서 테이블을 채워나가봅시다.

이 때, 동전리스트에 추가된 동전을 사용하지 않고 만들 수 있는 방법은 그냥 바로 윗 열에 해당하는 가짓수를 가져오면 됩니다.

그 부분이 이전 동전리스트에 대한 해당 '(원)'을 만들 수 있는 방법이니까요. 

하지만, 여기서 끝나는 것이 아니라, 우리는 추가된 동전을 가지고도 만들 수 있는 방법을 더해줘야 합니다.

그것은 간단합니다. 해당 '(원)'에서 추가된 동전의 가치(=이것도 또다른 '(원)'이겠죠)를 빼줌으로써, 그 값을 만들 수 있는 방법을 그대로 더해주면 됩니다.

 

이해가 안가신다면, 예시를 들어 설명드리겠습니다.

위 테이블(4행 6열)에서 3행 5열의 값은 동전리스트가 [1,2]를 가지고 4원을 만드는 방법의 수 입니다.

앞서 말했듯이, 동전리스트에 추가된 동전이 없는 직전의 행에서 4원을 만드는 방법, 즉 추가된 '2'원을 사용하지 않고, 오직 '1'원만을 이용해서 4원을 만들 수 있는 방법은 그 직전 행의 같은 열(2행 5열)의 값인 1 가지가 되겠죠.

 

하지만, 우리는 여기서 끝나는 것이 아니라고 했습니다.

추가된 동전 '2'원을 가지고도 만들 수 있는 방법을 더해줘야 합니다.

즉, 만들고자 하는 '4'원에서 추가된 동전 '2'원을 빼주면 '2'원이 되는데, 동전리스트 [1,2]를 가지고 '2'원을 만들 수 있는 방법은

3행 3열에 있는 값인 2가지 입니다.

 

이렇게 해서, 총 (1가지 + 2가지)=3가지 가 동전리스트 [1,2]를 사용해서 '4'원을 만들 수 있는 가지수가 되는 것입니다.

 

이 때, 만들고자 하는 '원'에서 추가된 동전의 가치를 뺐을 때, 음수가 된다면, 그냥 방법이 없는 것이므로, 무시하면 되겠습니다.

예를 들자면, 4행 3열은 동전리스트 [1,2,5]로 '2'원을 만드는 방법인데, 추가된 동전 '5'원을 사용하지 않고 만들 수 있는 방법은 그 직전 행 같은 열에 있는 2가지가 됩니다.

하지만, 추가된 동전 '5원'으로 '2'원을 만들고자 동전을 사용할 수 없기에, 즉, 2-5 = -3으로 음수가 되기에, 추가된 동전으로 해당 '원'을 만드는 방법은 여기서는 무시하면 되겠습니다.

 

 

해당 규칙을 식으로 표현한 것이

table[row][col] = table[row-1][col] + table[row][col-coins[row-1]] 입니다.

해당 로직을 코드로 그대로 옮겨봅시다.

class Solution(object):
    def change(self, amount, coins):

        n = len(coins)
        dp = [[0 for _ in range(amount+1)] for _ in range(n)]
        for i in range(n):
            dp[i][0] = 1
    
        for i in range(n):
            for j in range(1,amount+1):
                dp[i][j] = dp[i-1][j]
                if (j - coins[i] >= 0):
                    dp[i][j] += dp[i][j-coins[i]]

        return dp[n-1][amount]

이렇게, 2차원 dp로 풀 수 있는데, 여기서 메모리 누수를 줄이기 위해 조금 더 간편하게 1차원 dp로 풀어보면 아래처럼 정리할 수 있습니다.

class Solution(object):
    def change(self, amount, coins):

        dp = [0] * (amount+1)
        dp[0] = 1

        for i in range(len(coins)):
            for j in range(1,amount+1):
                if (j - coins[i] >= 0):
                    dp[j] += dp[j-coins[i]]

        return dp[amount]

이렇게 하면, 메모리 복잡도가 O(N*M)에서 O(N) (N은 amount) 로 감소하게 됩니다.

---

그럼, 다른 방식으로 시각화를 해볼까요?

recursion을 사용해서 풀어본다면, 어떻게 코드를 짜야할까요?

먼저, 시각화한 테이블을 살펴봅시다.

recursion

처음 시각화한 테이블과 비슷한데, recursion을 이해하기 쉽도록 하기 위해, 순서만 바꿨을 뿐입니다.

class Solution(object):
    def change(self, amount, coins):

        cache = {}

        def dfs(i,a):

            if a == amount:
                return 1
            if a > amount:
                return 0 
            if i == len(coins):
                return 0
            if (i,a) in cache:
                return cache[(i,a)]

            cache[(i,a)] = dfs(i,a+coins[i]) + dfs(i+1,a)
            return cache[(i,a)]

        return dfs(0,0)

로직은 위의 dp 내용과 똑같습니다. 여기서 dfs함수의 i는 coins 배열에서의 인덱스이고, a는 만들고자 하는 amount '원'에 해당합니다.

a원을 만들기 위해서 coins[i]를 사용해서 만드는 방법과 그대로 스킵하는 방법을 다 더해주는 로직은 동일합니다.

 

시간복잡도 역시 O(N*M) 의 복잡도를 가지며, 공간복잡도도 O(N*M)을 가집니다. (2차원 DP와 동일)

(N은 amount, M은 coins의 길이)

이상으로 팰린드롬과 관련한 518. Coin Change II 문제를 정리해봤습니다.