[백준] 1,2,3 더하기

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

fun main() = with(Scanner(System.`in`)) {
    val number = nextInt()

    val array = Array(number) { 0 }
    for (i in array.indices) {
        array[i] = nextInt()
    }

    for (i in array) {

        var count = 0;
        fun dfs(total: Int) {
            if (total >= i) {
                if (total == i) {
                    count++
                }
                return
            }

            dfs(total + 1)
            dfs(total + 2)
            dfs(total + 3)
        }
        dfs(total = 0)

        println(count)
    }
}

 

위에는 백패킹 방법 - 시간초과

 

아래는 dp로 푸는방법

fun main() = with(Scanner(System.`in`)) {
    val number = nextInt()

    val array = Array(number) { 0 }
    for (i in array.indices) {
        array[i] = nextInt()
    }
    val max = array.max()
    val items = Array(max + 1) { 0L }
    if (max >= 1) {
        items[1] = 1
    }
    if (max >= 2) {
        items[2] = 2
    }
    if (max >= 3) {
        items[3] = 4
    }

    for (i in 4 .. max) {
        items[i] = (items[i - 1] % 1000000009) + (items[i - 2] % 1000000009) + (items[i - 3] % 1000000009)
    }
    for(i in array){
        println(items[i] % 1000000009)
    }
}