백준 [15989] kotlin

[문제]

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

15989번: 1, 2, 3 더하기 4

[풀이]

동전 교환 문제라고 볼 수 있다. 

이 문제를 동전 교환 문제로 표현한다면, 

1원,2원,3원으로 특정 금액 만드는 경우 수를 찾아야 한다.

 

문제에 만들어야 하는 수의 최대는 10000이므로, 0부터 10000까지 경우를 미리 찾아놓으면 된다.

 

동전 교환 알고리즘은 다음은 식으로 표현이 가능하다 .

비용을 저장해 놓은 배열을 cost라 하고, 경우의 수를 저장해 놓은 배열을 dp라고 한다면. 아래의 공식을 만족한다.

if(i < j) dp[i][j] = dp[i-1][j]
else dp[i][j] = dp[i][j-cost[i]] + dp[i-1][j]

이 공식을 이용하여, dp 배열을 갱신을 해주면 된다.

 

1,2,3으로 k를 만드는 경우의 수는 아래와 같다.

dp[3][k]

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main()
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val N = br.readLine().toInt()

    var dp = ArrayList<IntArray>()
    dp.add(IntArray(10001,{0}))
    dp[0][0] = 1
    repeat(3)
    {
        dp.add(IntArray(10001,{0}))
    }
    for(i in 1 ..3){
        for(j in 0..10000)
        {
            if(j < i) dp[i][j] = dp[i-1][j]
            else dp[i][j] = dp[i][j-i] + dp[i-1][j]
        }
    }
    repeat(N)
    {
        bw.write(dp[3][br.readLine().toInt()].toString() + "\n")
    }
    bw.flush()
    bw.close()
}