[BOJ] 2748 - 피보나치 수 2 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 피보나치 수를 구해 나간다.

 

 

풀이 #1 (Python)

 

피보나치 수를 저장하기 위해 0으로 채워진 N+1 크기의 리스트 dp를 생성하고, dp[1]의 값으로 1을 할당한다.

for문에서 2부터 N까지의 수에 대해 앞의 두 피보나치 수의 합으로 피보나치 수를 계산하고, dp에 저장한다.

 

N = int(input())
dp = [0]*(N+1)
dp[1] = 1
for i in range(2, N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N])

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 입력에 대한 결과값이 number 자료형의 범위를 벗어나므로 BigInt를 사용한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
let dp = Array(N+1).fill(BigInt(0));
dp[1] = BigInt(1);
for (let i=2; i<=N; i++) dp[i] = dp[i-1]+dp[i-2];
console.log(String(dp[N]));