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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12951

문제 설명

피보나치 수는 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을 완성해 주세요.

내 풀이

function solution(n) {
    // 동적 계획법을 사용한 풀이
    // index = n, value = F(n)
    const memo = [0,1]
    for (i = 2; i <= n; i++) {
        memo.push((memo[i-2] + memo[i-1])%1234567)
    }
    return memo[n] 
}

 

이 부분에서 의문이 들었던 것은 이 부분이다.

n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수 => 즉, n 번째이다.

function solution(n) {
    // ...
    for (i = 2; i <= n; i++) {
        memo.push((memo[i-2] + memo[i-1]))
    }
    return memo[n] %1234567
}

그렇다면, return 하는 값에 나눗셈을 한 후, 나머지를 출력해야 되는데 애러가 발생했습니다.

그래서 남들이 하는 방식인 반복문 중에 계산하는 것으로 넣었더니 실행되었습니다.

 

아무래도 문제가 잘못 된 것이 아닌가 싶다.

다른 사람의 풀이

대부분 비슷하다.

오늘 배운 점

DP의 가장 간단한 예시인 피보나치 수열을 수행했습니다.