[프로그래머스] 멀리뛰기 - 자바스크립트

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

프로그래머스

피보나치 수열이라는 것을 알기까지 시간이 좀 걸렸다. 1부터 5까지의 케이스를 나타내보겠다.

1(1)

11(2)
2(2)

111(2+1)
12(1+2)
21(2+1)

1111(3+1)
112(2+2)
121(3+1)
211(3+1)
22(2+2)

11111(4+1)
1112(3+1)
1121(4+1)
1211(4+1)
2111(4+1)
122(3+2)
212(3+2)
221(4+1)

괄호를 쳐서 표현한 것은, n에 있는 것들은 n-2의 값과 n-1에 각각 1과 2를 붙여서 만든 값이라는 것을 볼 수 있다. 하지만, dp를 이용하여 list에 저장하여 푸는 것이 더 빠르기 때문에 list를 만들어서 풀이를 하겠다.

1. 편하게 계산을 하기 위해, n+1의 길이인 array에 0을 넣는다, n+1을 사용하는 이유는 list(n)은 n에 관련된 값으로 index-1을 사용하지 않기 위해서이다.

    const list = Array.from({length:n+1}).fill(0)

2. 1일 때는 1, 2일 때는 2이다

    list[1]=1
    list[2]=2

3. 피보나치 수열을 array에 저장을 한다. 그리고 1마다 증가하며 계속 진행한다

        function pibo(number){
            list[number] = list[number-1]%1234567+list[number-2]%1234567
            if(number<n){
          	  pibo(number+1)
            }
        }

4. 피보나치 수열 함수를 3일 때 실행한다. 사실 3 이상부터라는 조건을 붙여도되지만.. 클린하기 위해.. 그냥 사용했다

5. list[n]을 조건에 맞게 1234567의 나머지로 나누고 return 한다

 

전체풀이

function solution(n) {
    const list = Array.from({length:n+1}).fill(0)
    list[1]=1
    list[2]=2
        function pibo(number){
        list[number] = list[number-1]%1234567+list[number-2]%1234567
        if(number<n){
        pibo(number+1)
        }
        }
        pibo(3)
    return list[n]%1234567
}