μ€λλ μμ€μ΄λ λμ νλ‘κ·Έλλ° μμ μ‘°κ΅λ₯Ό νκ³ μλ€. μλΉ κ° μμ ν λ΄μ©μ νμλ€μ΄ μ μ΄ν΄νλμ§ λ¬Έμ λ₯Ό ν΅ν΄μ νμΈν΄λ³΄μ.
μ€λμ nμ νΌλ³΄λμΉ μλ₯Ό μ¬κ·νΈμΆκ³Ό λμ νλ‘κ·Έλλ°μΌλ‘ ꡬνλ μκ³ λ¦¬μ¦μ λ°°μ λ€. μ¬κ·νΈμΆμ λΉν΄ λμ νλ‘κ·Έλλ°μ΄ μΌλ§λ λΉ λ₯Έμ§ νμΈν΄ 보μ. μλ μμ¬ μ½λλ₯Ό μ΄μ©νμ¬ nμ νΌλ³΄λμΉ μλ₯Ό ꡬν κ²½μ° μ½λ1 μ½λ2 μ€ν νμλ₯Ό μΆλ ₯νμ.
νΌλ³΄λμΉ μ μ¬κ·νΈμΆ μμ¬ μ½λλ λ€μκ³Ό κ°λ€.
fib(n) {
if (n = 1 or n = 2)
then return 1; # μ½λ1
else return (fib(n - 1) + fib(n - 2));
}
νΌλ³΄λμΉ μ λμ νλ‘κ·Έλλ° μμ¬ μ½λλ λ€μκ³Ό κ°λ€.
fibonacci(n) {
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i - 1] + f[i - 2]; # μ½λ2
return f[n];
}
첫째 μ€μ n(5 β€ n β€ 40)μ΄ μ£Όμ΄μ§λ€.
μ½λ1 μ½λ2 μ€ν νμλ₯Ό ν μ€μ μΆλ ₯νλ€.
μμ μ
λ ₯ 1
5
μμ μΆλ ₯ 1
5 3
μμ μ
λ ₯ 2
30
μμ μΆλ ₯ 2
832040 28
const input = require('fs').readFileSync('/dev/stdin').toString().trim()
const num = Number(input)
let [recursiveCount, dpCount] = [0, 0]
// μ¬κ· νΌλ³΄λμΉ
function recursiveFibonacci(n) {
if(n <= 2) {
recursiveCount++
return 1
}
return recursiveFibonacci(n-1) + recursiveFibonacci(n-2)
}
// DP νΌλ³΄λμΉ
function dpFibonacci(n) {
// νΈμλ₯Ό μν΄ 0μ μμ λ£μ΄μ€, μ¦ n=5 μ΄λΌλ©΄ 5λ°ν
const fibArr = [0, 1, 1]
for(let i = 3; i <= n; i++) {
const curFibonacci = fibArr[i-1] + fibArr[i-2]
dpCount++
fibArr.push(curFibonacci)
}
return fibArr.at(-1)
}
recursiveFibonacci(num)
dpFibonacci(num)
console.log(recursiveCount, dpCount)