<aside> 🌐
</aside>
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.
1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...
자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!
자연수 n(1 ≤ n ≤ 116)이 주어진다.
예제) 10
n번째 피보나치 비스무리한 수를 출력한다.
예제) 19
풀이 자체는 쉽다고 생각했습니다. 피보나치 재귀함수를 응용하기로 했습니다.
function likeFibo(n, memo={}) {
if(n <= 3) return 1;
if(memo[n] !== undefined) return memo[n];
memo[n] = likeFibo(n - 1, memo) + likeFibo(n - 3, memo);
return memo[n];
}
console.log(likeFibo(num))
하지만, 틀렸다고 나왔습니다. 백준은 제한 시간내에 결과를 도출해야하고 기본적으로 자바스크립트의 재귀 깊이에 제한이 있으므로 시간초과 혹은 스택 오버플로일 것이라고 예상하여 Bottom-Up방식으로 개선했습니다.
const dp=[0, 1, 1, 1];
for(let i = 4; i <= num; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
console.log(dp[num])
런타임 에러(TypeError)가 납니다.
구글링해 본 결과, BigInt를 사용해야하는 문제였습니다. n이 116으로 주어지는 경우 답은 139,423,224,561,697,880,139,045,716,414,505 입니다. 29자리의 수로 자바스크립트 숫자 타입의 범위(9,007,199,254,740,991)를 넘어섭니다.
따라서 BigInt를 사용해 코드를 수정해보았습니다. 자바스크립트에서는 정수 뒤에 n을 붙이면 BigInt로 인식되므로 연산하는 모든 값에 n을 붙입니다. 그리고 BigInt의 결과는 .toString()으로 출력해야 합니다.
⬇️ BigInt 사용 Top-Down 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const num = +input;
function likeFibo(n, memo = {}) {
if (n <= 3) return 1n;
if (memo[n] !== undefined) return memo[n];
memo[n] = likeFibo(n - 1, memo) + likeFibo(n - 3, memo);
return memo[n];
}
console.log(likeFibo(num).toString());
⬆️ BigInt 사용 Bottom-up 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const n = +input;
const dp = new Array(n + 1).fill(0n);
dp[1] = 1n;
if (n >= 2) dp[2] = 1n;
if (n >= 3) dp[3] = 1n;
for (let i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
console.log(dp[n].toString());
✚ 추가적인 개선
n으로 116이 주어지는 경우, 배열의 크기가 116 이상이어야 하기 때문에 좀 더 효율적인 방식을 고민해보았습니다. 문제는 n번째 수만 구하면 되므로 배열을 크게 둘 필요가 없습니다. 즉, 메모리 공간을 개선하여 최적화하도록 다음과 같이 개선할 수 있습니다.
if (n <= 3) {
console.log('1');
} else {
let a = 1n, b = 1n, c = 1n, result = 0n;
for (let i = 4; i <= n; i++) {
result = c + a;
[a, b, c] = [b, c, result];
}
console.log(result.toString());
}
n - 1(a), n - 2(b), n - 3(c)까지의 공간만 써서, 하나씩 미뤄서 result값을 구하는 방식입니다. 이는 기존에 O(n)이던 공간복잡도를 O(1)로 줄여서 메모리용량을 줄일 수 있습니다.