백준 9084 동전 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/9084

9084번: 동전

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

풀이

dp[a][b] = 오름차순 정렬된 코인 중 a까지의 코인을 가지고 있을 때 b원을 만들 수 있는 경우의 수

어떻게 이렇게 dp를 정의할 수 있는지 생각해 보자.

우선 1원짜리 코인을 가지고 있을 때 7원까지 만들 수 있는 경우의 수를 그래프로 나타내면 다음과 같다.

	0	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1	1
2

이어서 2원짜리 코인도 가지고 있는 경우는?

1,2원짜리 동전을 합쳐서 2원을 만드는 상황을 예로 들어보자.

아래 그래프와 같이 우선 1원짜리 코인을 가지고 2원을 만든 경우의 수(dp[1][2])가 있다.

2원을 2원짜리 코인으로 만드는 것은 2 - 2 원을 만드는 경우의 수에 2만 더하면 되므로 2원짜리 코인으로 0을 만드는 경우의 수 (dp[2][0])을 더하면 된다.

	0	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1	1
2	1	1	2
3

즉 점화식은 dp[currentCoin][x] = dp[beforeCoin][x] + dp[currentCoin][x-currentCoin]이다.

아래처럼 그래프를 완성시켜보고 dp를 코드로 옮기면 끝.

	0	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4
3	1	1	2	3	4	5	7	8

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){

    repeat(getInt()){
        //input
        val n = getInt()
        val coins = getIntList()
        val dest = getInt()
        //solve
        val dp = Array(coins.size){
            IntArray(dest+1){
                if(it==0) 1 else 0
            }
        }
        for(i in coins.indices){
            val coin = coins[i]
            for(money in 1..dest){
                if(i-1 >=0){
                    dp[i][money] += dp[i-1][money]
                }
                if(money - coin >=0){
                    dp[i][money] += dp[i][money-coin]
                }
            }
        }
        //output
        write("${dp[coins.size-1][dest]}\n")
    }

    close()
}