BOJ : 24416 알고리즘수업 피보나치(1) (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split(' ');
const c = console.log

n = Number(input[0])

let dp = []

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2

for(let i = 4 ; i < 41 ; i++){
    dp[i] = dp[i-1] + dp [i-2]
}

let code1 = dp[n]

let code2 = n-2

c(`${code1} ${code2}`)

 

풀이

우선, 코드2 같은경우에는 -2 만큼의 횟수만큼만 실행되고

코드1은 피보나치수가 1,2인 경우 1번, 3인 경우 2번 실행되고 4부터 점화식이 존재하는데

fib(4) = fib(2) + fib(3) = fib(2) + fib(2) + fib(1) 임을 알게 되어서 

 

dp테이블을 작성해 dp[i] = dp[i-1] + dp[i-2] 를 해주었습니다.

 

문제

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1