Dynamic Programming [2] - Coin Change(1) 최소값

https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

저번 코테에서 DP를 DP인줄 알면서 못풀었기 때문에 DP 20문제 도전하겠다.

20문제 풀고 DP 못풀면 코테 포기한다

 

문제)

갖고있는 동전 배열이 있다. 배열의 각각의 수는 동전의 값을 의미한다 (1원, 3원..)

동전의 갯수는 무한이라고 친다. 

n원을 거슬러줘야 할 때, n원을 만들기 위한 가장 적은 수의 동전 갯수를 구하라

단, 가진 동전으로 n원을 만들 수 없다면 -1을 리턴하라

 

예제)

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

1원짜리, 2원짜리, 5원짜리가 있고, 11원을 만들어야 한다면

1원을 만들 수 있는 최소 갯수 -> 11원을 만들 수 있는 최소 갯수 까지 누적하면서 구한다.

 

점화식을 구해야한다.

amount = 0 일때 동전갯수는 0개

amount = min(coins) 일때 동전갯수는 1개

amount = n, n원을 만들 때 필요한 최소한의 동전 갯수는 (n원 - 동전1, n원 - 동전2, n원 - 동전3, ... ) 중 최소값 + 동전 1개 이다.

 

식으로 하면, 거스름돈 n원일때 필요한 최소 동전갯수를 A[n], x번째 동전을 coin[x]이라고 할때 

A[n] = min(A[n-coin[1]], A[n-coint[2]], A[n-coin[3] ... ) + 1

그러면 코드 짜보면~

fun coinChange(coins: IntArray, amount: Int): Int {
    val maxValue = amount+1 // 거스름돈 보다 1원 큰 돈
    val A = IntArray(amount+1)
        
    // min 비교를 위해 가장 큰 값으로 미리 채운다
    A.fill(maxValue)
        
    A[0] = 0
    for (n in 1 .. amount) {
        for (i in 0..coins.size-1) {
            if (coins[i] <= n) {
                A[n] = Math.min(A[n], A[n-coins[i]] + 1)
            }
        }
    }
    //illegal 한 경우 -1 리턴해준다.
    return if(A[amount] > amount) -1 else A[amount]
}