Level 2 ) 멀리 뛰기 ⭐️

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

n은 1 이상, 2000 이하인 정수입니다.

입출력 예

n	result
4	5
3	3

풀이

팩토리얼을 이용한 방법을 생각해보았다.

1. 2의 개수는 n을 2로 나눠서 내린 값으로 설정하고, 1의 개수는 n을 2로 나눈 나머지로 설정한다.
2. 팩토리얼 함수를 따로 만든다.
3. 2의 개수가 0보다 같거나 클 때까지 Factorial을 이용해 가능한 각 경우마다 가능한 케이스를 구해 answer에 더해준다.
   (전체 개수)! / (1의 개수)! * (2의 개수)! = 가짓수
4. 2의 개수는 1씩 감소시키고, 1의 개수는 2씩 증가시킨다.
5. answer를 1234567로 나눈 나머지를 return한다.

예시 ) n = 4

1. 4 / 2 = 2(two), 0(one)
   answer = 1;
2. 2 / 2 = 1(two), 2(one)
   answer = 1+3;
3. 1 / 2 = 0(two), 4(one)
   answer = 1+3+1;

function solution(n) {
    let answer = 0;
    let one = n % 2;
    let two = Math.floor(n/2);
    
    function Factorial(num){
        let a = 1;
        if(num === 0) return 1;
        for(let i=1;i<=num;i++){
            a *= i;
        }
        return a;
    }
    while(two >= 0){
        answer += Factorial(two+one) / (Factorial(two) * Factorial(one));
        two--;
        one+=2;
    }
    return answer % 1234567;
}

결과

테스트케이스 6번까지만 맞았다.
2000을 입력해보니 null이 나온다..!
입력값이 너무 커서 오버플로우가 발생한듯 하다.

다른 방법이 있나 찾아봤는데, 경우의 수를 쭉 구해보면 피보나치 수열의 형태를
띈다고 한다.
참고 | https://taesung1993.tistory.com/77

따라서 피보나치를 구해주면 된다.

1. 재귀를 이용한 방식

function jumpCase(num) {
  if (num === 1) return 1
  if (num === 2) return 2
  return jumpCase(num-1) + jumpCase(num-2)
}

2. DP를 이용한 방식

function solution(n) {
    var answer = 0;
    var dp=[];
    dp[1]=1;
    dp[2]=2;
    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2] %1234567;
    }
    answer=dp[n];
    return answer%1234567;
}