URL : https://www.acmicpc.net/problem/24416
24416번: 알고리즘 수업 - 피보나치 수 1
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍
www.acmicpc.net
[ RESULT ]
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() {
val n = br.readLine().toInt()
val dpCnt = 0
bw.write("${fibonacci_recursion(n)} ${fibonacci_dp(n, dpCnt)}")
br.close()
bw.close()
}
fun fibonacci_recursion(N: Int): Int {
return if(N == 1 || N == 2) {
1
}
else (fibonacci_recursion(N-1) + fibonacci_recursion(N-2))
}
fun fibonacci_dp(N: Int, cnt: Int): Int {
val mList = MutableList(N + 1) { 0 }
mList[1] = 0
mList[2] = 1
var dpCnt = cnt
for (i in 3..N) {
dpCnt++
mList[i] = mList[i - 1] + mList[i - 2]
}
return dpCnt
}
Baekjoon(Kotlin) - 11659. 구간 합 구하기 4 (0) | 2023.09.09 |
---|---|
Baekjoon(Kotlin) - 11054. 가장 긴 바이토닉 부분 수열 (0) | 2023.09.08 |
Baekjoon(Kotlin) - 11053. 가장 긴 증가하는 부분 수열 (3) | 2023.09.07 |
Baekjoon(Kotlin) - 9663. N-Queen (0) | 2023.09.06 |
Baekjoon(Kotlin) - 2580. 스도쿠 (0) | 2023.09.05 |