[LeetCode/Kotlin]Medium - 518. Coin Change II

Coin Change II - 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 number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

 

풀이

나의 풀이법

풀이 접근 과정

처음엔 dfs를 이용해 풀었지만 시간 초과가 났다.

이건 무조건 dp를 이용해 풀어야 하는 문제였는데 나는 dp를 잘 모르기 때문에 인터넷에서 힌트이자 답을 얻었다.

내가 참고한 코드는 프로그래머스의 동전 거스름돈 문제였다.

최종 소스코드

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val dp = IntArray(amount+1) { 0 }
        dp[0] = 1

        coins.forEach {
            for (i in it .. amount) {
                dp[i] += dp[i-it]
            }
        }

        return dp[amount]
    }
}

동전 조합의 경우의 수를 저장하기 위한 DP 배열을 선언한다. (dp[i]는 금액 i를 만들 수 있는 경우의 수를 나타냄)

배열은 금액 amount + 1 크기로 생성되며, 초깃값은 모두 0으로 설정되지만 dp[0]을 1로 초기화한다. 이는 금액 0을 만들기 위해 동전을 사용하지 않는 경우 1가지가 존재함을 의미한다.

coins 배열의 각 동전 가치(coin)에 대해 반복하며 내부에서는 금액 coin부터 amount까지의 범위에서 반복한다. 현재 가치의 동전을 사용하여 금액 i를 만들려고 할 때, dp[i] 값을 dp[i - coin] 값과 더해준다. 이는 현재 금액에서 현재 가치의 동전을 뺀 금액을 만들 수 있는 경우의 수를 현재 경우의 수에 더해준다는 의미입니다.

그렇게 만들어진 dp[amount] 값을 리턴한다.

 

---

Comment

dp는 언제나 어렵다 ㅠㅠ

dfs도 처음엔 어려웠던 것처럼 이것도 풀다보면 익숙해지겠지?