Dynamic Programming[3] - coin 경우의 수

https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 

The Coin Change Problem | HackerRank

문제)

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

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

n원을 거슬러줘야 할 때, n원을 만드는 동전의 조합의 수를 구하라

 

예제)

Sample Input

타겟금액, 동전갯수

동전 액면가들

4 3
1 2 3

Sample Output

4

Explanation

There are four ways to make change for  using coins with values given by :

1. {1,1,1,1}
2. {2,1,1}
3. {2,2}
4. {3,1}

이번에도 금액별로 구해서 더하려고 했더니, 조합이라서 {2, 3}과 {3,2}를 별개로 쳐서 안됨

그래서 동전으로 돌아야함

 

동전을 coin [0~x] 로 만들 수 있는 target 금액을 더한다

 

코인 1원~3원짜리로 (0원~4원)를 만들 수 있는 경우의 수

액면가 / 목표금액	0원	1원	2원	3원	4원
1원짜리	0	{1}	{1,1}	{1,1,1}	{1,1,1,1}
2원짜리사용	0	0	{2}	{2,1}	{2,1,1} {2,2}
3원짜리	0	0	0	{3}	{3,1}
총 경우의 수	0	0	2	3	4

 

사용할 수 있는 코인을 하나씩 더 추가하면서 경우의 수를 늘려나가야 했는데

목표금액으로 더하려고 하니 잘 되지 않았다.

 

점화식으로 표현하면 A[n]이 n원을 만들 수 있는 경우의 수, x+1개의 각각의 동전 가격을 coins[0~x] 라고 할 때,

 

A[0] 즉 나 자신의 코인으로 만들수 있는 경우는 1으로 하고,

A[n] = ∑A[n-coins[0~x] (단, coins[] < n 인 경우만)

 

 

fun getWays(targetMoney: Int, c: Array<Long>): Long {

    val A = LongArray(targetMoney+1)

    A[0] = 1;

    

    val coins  = c.map{it.toInt()}

    val coinMaxIdx = coins.size - 1

    

    for (coinIdx in 0 .. coinMaxIdx) {

        for(money in coins[coinIdx] .. targetMoney) {

            if (A[money-coins[coinIdx]] > 0){

                A[money] += A[money-coins[coinIdx]]

            }

        }

        println(A.toList())

    }

    return A[targetMoney]

}

​