[프로그래머스] 피보나치 수

문제 요약

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 입니다. 이때 2이상의 n이 주어질때 n번째 피보나치수를 1234567로 나눈 나머지를 구하세요.

 

나의 생각

최초 배열에 [0, 1]으로 초기화 후 반복문을 통해서 F(n) = F(n-1) + F(n-2)의 공식에 따라 n까지의 피보나치 수를 구합니다. 간단한 문제이지만 주의 해야하는 것은 n이 10만이 되면 정수를 담을 수 있는 사이즈를 초과하게 됩니다.

 

배열에 저장할 때 1234567을 나눈 나머지 값을 저장해 주어야 합니다.

 

나머지를 구하는 것이기 때문에 나머지 값으로 피보나치 수를 구해도 동일하게 구할 수 있습니다.

 

function solution(n) {
    const list = [0, 1];

    for (let i = 2; i <= n; i += 1) {
        list[i] = (list[i - 1] + list[i - 2]) % 1234567;
    }

    return list[n];
}