[BOJ] 1, 2, 3 더하기 in Python & Kotlin

문제풀러 가기!

쉬운 DP 문제였습니다.

문제에서는 n이 11까지로 한정되어 있기 때문에 11개의 배열을 만들고 이를 통해서 memoization을 진행하면 됩니다.

memoization을 진행할 배열의 이름을 dp라고 한다면

수식은 다음과 같습니다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

이를 통해 빠르게 문제를 풀 수 있었던 문제였습니다.
Python의 경우 알고리즘 문제 풀이 시 print 함수의 제약이 그렇게 크지 않는 것으로 알고 있습니다. 그래서 여러 번 사용해도 문제가 통과되는 경우가 좀 있습니다. 예를 들어서 print를 최대 10만번 사용해야 했던 문제의 경우에도 통과됐던 기억이 있습니다. 하지만, kotlin의 경우 println을 많이 사용하면 문제가 발생할 수 있기 때문에 좀 더 효율적인 출력을 위해 stringBuilder를 사용했습니다.

아래는 Python 풀이입니다.

import sys

input = sys.stdin.readline

T = int(input())
dp = [0] * 12
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 12):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(T):
    print(dp[int(input())])

다음은 Kotlin 풀이입니다.

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

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val T = br.readLine().toInt()

    val dp = IntArray(12){0}

    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    for (i in 4 until 12) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    }

    val sb = StringBuilder()
    var n: Int
    for (i in 0 until T) {
        n = br.readLine().toInt()
        sb.append("${dp[n]}\n")
    }
    println(sb)
}

개발은 예술이고 서비스는 작품이다.