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

🌭 문제 설명

피보나치 수는 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 이하인 자연수입니다.

---

🎁 입출력 예시

• 입출력 예 #1

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

---

😎 나의 풀이

function solution(n) {
  if (n === 1 || n === 2) {
    return 1; // F(1)과 F(2)는 1
  }

  let a = 1,
    b = 1; // 초기값 F(1) = a, F(2) = b

  for (let i = 3; i <= n; i++) {
    let temp = (a + b) % 1234567; // 계산된 값을 1234567로 나눈 나머지
    a = b;
    b = temp;
  }

  return b;
}

1. 피보나치 수열의 f(1) 과 f(2)는 1이므로 return 1
2. a와b는 1번째,2번째 값이므로 1로 지정
3. n이 3 이상일 경우 f(3) 부터 f(n)까지 계산한다.
4. a와b를 더한값을 1234567로 나누어서 큰 정수의 계산을 방지한다.
5. 이전 단계에서 b에 저장된 값은 F(n-1)의 값으로 다음 계산에서 사용한다.
6. 현재 계산된 피보나치 값을 b에 저장하여 F(n)의 값으로 사용한다.
7. 반복문이 끝나면 변수 b는 F(n) 값을 가지고 있으므로 반환하는데 이게 n번째 피보나치 수가 된다.

---

🧵 다른 풀이

function solution(n) {
    let answer = 0;
    let f0 = 0
    let f1 = 1;
    
    for(let i = 2; i <= n; i++){
        answer = (f0 + f1) % 1234567;
        f0 = f1;
        f1 = answer;
    }
    
    return answer;
}

1. f(0) 과 f(1) 의 초기값을 0과 1로 지정한다.
2. f(0) + f(1) 을 더한 피보나치 값을 1234567로 나눈 나머지값을 answer에 할당.
3. 이전에 저장된 F(i-1)을 다음 단계에서는 F(i-2)로 사용하기 위해 f0에 할당
4. 이번에 계산한 F(i)를 F(i-1)로 사용하기 위해 f1에 할당해준다.
5. 결과적으로 n번째 피보나치수를 리턴한다.

---

• 처음에 일반적인 재귀함수를 이용한 방법을 이용해서 풀었는데 테스트케이스에서 걸려서 구글링을 통해 DP의 바텀업방식으로 풀 수 있는 방식을 찾아서 해결@!