Coding Test/JavaScript
[프로그래머스/JS] 피보나치 수
ea_jung
2023. 7. 12. 23:34

이 문제는 문제를 이해하는데 시간이 걸렸다.
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수를 말하는데
0번째 피보나치 수가 0, 첫번째 피보나치 수가 1인건 정해져 있고 두번째 피보나치 수는 앞에 두개를 더한 1이 된다는 말이다.
예를 들어보면 0 1 1 2 3 5 8 13 과 같이 n-1 번째 수와 n-2번째 수가 더해져 n번째 수가 되는 법칙이 성립된다고 생각하면 된다.
그런데 문제에서 생뚱맞게 1234567 로 나누라고 해서 이게 뭐지 했는데 피보나치 수 44만 해도 2,971,215,073로 int의 값을 훨씬 넘은 수라 int 내에서 해결하기 위한 문제 의도라고 한다.
function getFibonacci(n) {
let fibonacciArr = [0, 1, 1];
for(let i = 3; i <= n; i++ ) {
fibonacciArr[i] = (fibonacciArr[i-1] + fibonacciArr[i-2]) % 1234567;
}
console.log(fibonacciArr)
return fibonacciArr[n]
}
function solution(n) {
const answer = getFibonacci(n)
return answer
}
코드는 정말 설명 그대로 적으면 돼서 어려울게 없는데 문제를 이해하는데 시간을 많이 쏟은 것 같다.
시간 복잡도 O(n) 걸린다.
반응형