문제

https://programmers.co.kr/learn/courses/30/lessons/12945

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5
  와 같이 이어집니다.

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

제한사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

Approach #1

f(0) = 0
f(1) = 1
f(2) = f(0) + f(1) = 0+1 = 1
f(3) = 1+1 = 2
f(4) = 3
f(5) = 5

0,1
1,1 //2
1,2 //3
2,3
3,5
5,8

Solution #1

function solution(n) {
  let fibo = [0,1];
  for(let i=2; i<=n; i++){
      fibo[0] %= 1234567;
      fibo[1] %= 1234567;
      
      let sum = fibo[0] + fibo[1];
      fibo[0]= fibo[1];
      fibo[1]= sum;
  }
  return fibo[1]%1234567;
}

Time Complexity

O(N)

Space Complexity

O(1)

Review

피보나치 수는 엄청 빠르게 증가하기 때문에 그냥 풀면 문제를 풀지 못한다.
(ex. 44번째 피보나치 수만 해도 2,971,215,073로 우리가 알고있는 int의 범위를 넘어감)

숫자 A, B, C가 있을때,
(A + B) % C = ( (A % C) + (B % C) ) % C 의 성질을 이용해서 문제를 풀어야함.
(int범위를 넘어가기 때문에, 문제에서 1234567로 나눈 나머지를 출력하라고 하는 것.)

TIL

Approach #2

dp테이블 만들어서 풀어볼것

Solution #2