백준 - 1,2,3 더하기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/9095

 

[문제 설명]

1,2,3을 사용해서 숫자를 만드는 방법이 몇개 있나 구하시오.

 

[접근 방법]

전형적인 동적프로그래밍 문제.

dp[1] = 1 => 1
dp[2] = 1+1 => 2
dp[3] = 1+1+1, 1+2, 2+1, 3 => 4

4부터가 고민이 될 수 있는데, 여기서 4를 만드는 방법은 3가지가 있습니다.

4 = 1 + 3

4 = 2 + 2

4 = 3 + 1

즉, 1을 만드는 방법과 2를 만드는 방법 그리고 마지막으로 3을 만드는 방법에 총합이 됩니다.

최종 점화식은 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]이 됩니다.

 

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cntOfTestcase = readLine().toInt()
    var max = Int.MIN_VALUE
    val array = IntArray(cntOfTestcase)

    repeat(cntOfTestcase) { idx ->
        val dpNum = readLine().toInt()
        array[idx] = dpNum
        if (dpNum > max) {
            max = dpNum
        }
    }

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

    val answer = StringBuilder()
    for (idx in array) {
        answer.append(dp[idx]).append("\n")
    }
    println(answer.deleteCharAt(answer.length - 1).toString())
}