[백준] 9095번: 1, 2, 3 더하기 - Kotlin[코틀린]

문제

 

9095번: 1, 2, 3 더하기

 

---

풀이

 

 문제는 하나의 자연수를 1, 2, 3으로 조합하여 만드는 경우의 수를 구하는 것으로 우선 1, 2, 3을 만드는 경우의 수를 먼저 확인해보자.

 

 1을 만드는 경우의 수는 (1)으로 1개고, 

 2를 만드는 경우의 수는 (1 + 1), (2)로  2개, 

 3을 만드는 경우의 수는 (1 + 1 + 1), (1 + 2), (2 + 1), (3)으로 4개다.

 

 1, 2, 3을 조합하여 4를 만드는 방법은 (1 + 3), (2 + 2), (3 + 1)로 나타낼 수 있는데,

 

 (1 + 3)은 (1) + (1 + 1 + 1), (1) + (1 + 2), (1) + (2 + 1), (1) + (3)으로, 3을 만드는 경우의 수에서 1을 더한 것이다.

 (2 + 2)는 (2) + (1 + 1), (2) + (2)으로 2를 만드는 경우에서 2를 더한 것이다,

 (3 + 1)은 (3) + (1)으로 1을 만드는 경우의 수에서 3을 더한 것이다.

 모든 경우의 수를 모두 더하면 총 7개가 된다.

 

 5를 만드는 방법도 마찬가지로 (1 + 4), (2 + 3), (3 + 2) 3가지 경우로 나타낼수 있고, 4를 만드는 경우의 수 + 1, 3을 만드는 경우의 수 + 2, 2를 만드는 경우의 수 + 3이 되어 총 13개가 된다.

 

 위의 규칙을 점화식으로 만들면  dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] 이 된다. 문제에서 주어진 범위인 10까지 구하고 입력받은 수의 경우의 수를 출력하면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val dp = IntArray(11)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for(i in 4..10) {
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    }

    val sb = StringBuilder()
    val testCase = br.readLine().toInt()

    repeat(testCase) {
        sb.append("${dp[br.readLine().toInt()]}\n")
    }
    
    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}