쉬운 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)
}
개발
은 예술
이고 서비스
는 작품
이다.