2293번: 동전 1 - Kotlin

2293번: 동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

 

나의 풀이

 이 문제는 DP를 사용해야 하는 문제이다. 이 문제는 아래의 백준 문제와 유사하다. 

 

9095번: 1, 2, 3 더하기 - Kotlin

 

 위의 문제를 보게 되면 숫자가 1, 2, 3으로 정해져 있다. 이 숫자가 정해져 있지 않고 주어진다는 것이 다른 점이 된다. 다만DP를 채우는 방식은 다르다. 이 문제는 주어진 동전의 숫자를 가지고 채울 수 있는 K까지의 숫자에 집어넣게 된다. 

 

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }

    val coin = Array(n) { readLine().toInt() }

    val dp = IntArray(k + 1)

    dp[0] = 1

    for(i in 0 until n){
        for(j in 0..k){
            if (j - coin[i] >= 0)
                dp[j] += dp[j - coin[i]]
        }
    }

    println(dp[k])
}