2Level / 연습 문제 / 피보나치 수

문제 설명

 

문제 풀이 방법

• 피보나치 수를 구하는 방법은 내가 이전에 정리한 글을 참고해 DP접근법으로 문제를 해결하려했다.
  top-down방법은 시간초과가 발생해 통과하지 못했고,
  down-top으로 풀어봤지만 이 역시 마찬가지 였다....
• 계속 고민해 보았지만 결국 다른 사람들이 질문한 글을 봤다.
  가장 잘 설명된 글에서 이렇게 말했다.
• 피보나치 수가 78번째 정도만 되어도 정수 범위가 JS에서 허용하는 범위보다 커져 에러가 발생한다.
  이를 방지하기 위해 문제에서 "1234567을 나눈 나머지를 리턴" 이라는 조건을 부여한것이다.
• 이때 글에 나온 %의 속성이 많이 흥미로웠다.
  (A+B)%C = ((A%C) + (B%C))%C 라는 속성이다.
  이 의미가 무엇인가 하면 1, 1, 2, 3, 5, 8에서 (8%1234567) = ((5%1234567)+(4%1234567))%1234567이라는 것이다.
  이는 큰 수로 예를 들어보자 [71]:  308061521170129, [72]:  498454011879264, [73]:  806515533049393 
  위의 속성과 같이 계산해 보면 818507 = (376191+442316)%1234567 이라는 것이다.
  실제로도 맞는 답이 나온다. 추가적으로 찾아본 글을 참고하자
• 이마 동작 범위내에서 코드가 동작하게 하기위한 장치이라 생각된다.
  처음 보는 개념이라 충격이였다....

 

내가 작성한 코드

const solution = (n) => {
    return func(n)%1234567
}

const func = (m) => {
    let arr = [0, 1, 1];
    for(let i=3; i<=m; i++){
        arr[i] = arr[i-1]%1234567 + arr[i-2]%1234567;
    }
    return arr[m]
}