DP : 동전 1 [백준 2293, Kotlin]

[문제]

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

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

[출력]
첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

[풀이]

골드 dp는 역시 어렵다.

리스트에 동전을 넣어두고 시작

key point : 동전 2로는 1을 만들 수 없다. 코인을 기준으로 인덱스에서 코인을 뺀 인덱스의 값을 더해준다.

ex) 동전 1, 2, 5 라면

 

동전 1

array[1] ~ array[10] 반복

array[1] = array[1] + array[0]

array[2] = array[2] + array[1]

array[3] = array[3] + array[2]

…

동전 2

array[2] ~ array[10] 반복

array[2] = array[2] + array[0]

array[3] = array[3] + array[1]

array[4] = array[4] + array[2]

…

동전 5

array[5] ~ array[10] 반복

array[5] = array[5] + array[0]

array[6] = array[6] + array[1]

…

 

[코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nk = br.readLine().split(" ").map { it.toInt() }
    val n = nk[0]
    val k = nk[1]
    val array = IntArray(k + 1) { 0 }
    val coins = mutableListOf<Int>()
    for (i in 0 until n) {
        val coin = br.readLine().toInt()
        coins.add(coin)
    }

    array[0] = 1

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

    println(array[k])
}

[출처]

 

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

2293번: 동전 1