230326 TIL - 프로그래머스 12945

---

12945

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

JavaScript

// solution 1 : BigInt 이용
function solution(n) {
    fibo = [0n, 1n];
    while (fibo.length <= n) {
        fibo.push(fibo[fibo.length-2] + fibo[fibo.length-1]);
    }
    return fibo[n] % 1234567n;
}

• n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가 오버플로우가 나므로 BigInt 자료형을 사용해야 함
• BigInt 는 Number 원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수를 표현할 수 있는 내장 객체
• BigInt는 정수 리터럴의 뒤에 n을 붙이거나(10n) 함수 BigInt()를 호출해 생성

// solution 2 : (A + B) % p = ((A % p) + (B % p)) % p 이용
function solution(n) {
    fibo_remainder = [0, 1];
    // (A + B) % p = ((A % p) + (B % p)) % p
    while (fibo_remainder.length <= n) {
        fibo_remainder.push((fibo_remainder[fibo_remainder.length-2] + fibo_remainder[fibo_remainder.length-1]) % 1234567);
    }
    return fibo_remainder[n];
}

• 일반적으로 알려진 나머지에 관련된 법칙 사용해서 풀이
• 단계마다 나머지 연산을 해줌으로써 오버플로우 사전에 방지

Python

def solution(n):
    fibo = [0, 1]
    while (len(fibo) <= n):
        fibo.append(fibo[len(fibo) - 2] + fibo[len(fibo) - 1])
    return fibo[n] % 1234567