[백준] 2293. 동전 1 (Kotlin)

문제 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

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

www.acmicpc.net

풀이

// [백준] 2293. 동전 1 (Kotlin)

import java.util.*

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val k = nextInt()
    val dp = Array(10001){0}
    val coin = Array(n){0}
    dp[0] = 1

    for(i in 0 until n){
        coin[i] = nextInt()
    }

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

    println(dp[k])
}

DP 문제로, 점화식을 떠올려보다가 떠오르지 않아서 다른사람들의 풀이를 참고하여 풀었다.

DP[n] = x (n을 만들 수 있는 경우의 수 = x)

로 DP에 저장한다.

예제처럼

n=3, k=10

의 값이 들어왔다면

동전에 대하여 각각 그 동전을 사용하여 만들 수 있는 경우를 더해준다.

1을 사용하여 1을 만들려면 1을 1개 사용하면 되고, (dp[1])

1을 사용하여 2를 만들려면 이미 1이 존재할 때 1을 사용하면 되고, (dp[2] += dp[1])

1을 사용하여 3을 만들려면 이미 2가 존재할 때 1을 사용하면 된다. (dp[3] += dp[2])

이런식으로 2와 5의 경우도 k까지 반복하면

k를 만들 수 있는 경우의 수를 구할 수 있다.