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

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

9095번: 1, 2, 3 더하기

문제 풀이

1. 주어진 문제를 푸는 방법은 두 가지가 있다.

2. 첫번째는 1을 만드는 개수 2를 만드는 개수 3을 만드는 개수 4를 만드는 개수를 구해 본다.

2-1. 1 -> 1

       2 -> 2

       3 -> 4

       4 -> 7

2-2. 2-1 과정에 DP 를 이용하여 아래의 점화식을 구할 수 있다.

       DP[n] = DP[n - 3] + DP[n - 2] + DP[n - 1]

3. 두번째는 dfs 를 이용한 완전 탐색을 통해서 경우의 수를 구한다.

3-1. 처음 시작을 0으로 해서 현재의 합과 입력값이 n 보다 작은 경우에 대해서 dfs 를 수행 한다.

코드

import java.io.*

var result = 0

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val T = br.readLine().toInt()

    repeat(T) {
        val n = br.readLine().toInt()
        val arr = intArrayOf(1, 2, 3)
        result = 0
        dfs(arr, 0, n)
        println(result)
    }
}

fun dfs(arr: IntArray, sum: Int, n: Int) {
    if (sum == n) {
        result++
        return
    }

    //println("$sum, $n $result")

    for (i in 0..2) {
        if (sum + arr[i] <= n) {
            dfs(arr, sum + arr[i], n)
        }
    }
}