[Lv.2] 멀리 뛰기 (피보나치 수열과 경우의 수)

프로그래머스

1. 문제

• 멀리 뛰기

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

입출력 예

4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

2-1. 풀이 (틀린 풀이)

function solution(n) {
    var answer = 0;
    
    let fac = (num)=>{ //팩토리얼
        if(num === 0){
            return 1
        }
        else{
            let a = num
            while(num !==1){
                a *= (num-1);
                num--
            }
            return a
        }
    }
    
    let nCr = (n,r) => { //조합 공식
        return fac(n)/(fac(n-r)*fac(r))
    }
    
    for(let i =0; i<=Math.floor(n/2); i++){ //2의 개수가 0개인 경우부터 n/2의버림수 까지
        answer += nCr(n-i,i) // 2의 개수에 따라 앞의n이 i만큼 변화하므로 nCr 경우의수를 고려함
    }
    answer = (answer) % 1234567 //그렇게해서 답을 1234567로 나눈 나머지를 리턴
    
    return answer;
}

실패! 

- 이유는 overflow현상. 매우 큰 정수 answer에 대해 overflow현상이 일어났기 때문.

- 그래서 이것저것 찾아보다가..

1칸까지 뛰는 방법은 1가지, 2칸까지 뛰는 방법이 2가지인 것은 쉽게 알 수 있습니다.이제 n칸까지 뛰는 방법은 다음과 같이 생각해 볼 수 있습니다.
[n - 1]번째 칸에서 1칸을 뛰어서 n번째 칸에 도착했다.[n - 2]번째 칸에서 2칸을 뛰어서 n번째 칸에 도착했다.
첫 번째 방법은 마지막에 1칸을 뛰어서 도착했고, 두 번째 방법은 마지막에 2칸을 뛰어서 도착했기 때문에, 위 두가지 방법 중 서로 중복되는 경우는 없습니다. 따라서 n번째 칸으로 뛰는 방법의 수는 [n-1]번째 칸으로 뛰는 방법 수 + [n-2]번째 칸으로 뛰는 방법의 수가 되며, 이는 피보나치 수열과 동일합니다.

쉽게 말해

10까지 도달하는 방법의 수는 (9까지도달하는 방법의 수) + (8까지도달하는 방법의 수) 

- 1칸뛰기와 2칸뛰기밖에 없기때문에

- 피보나치!

function solution(n) {
    let fib = [0,1,2]; //정해진 피보나치 초기숫자
    
    for(let i =3; i<=n; i++){
        fib.push((fib[i-2] + fib[i-1])%1234567) 
        //오버플로우 방지를 위해 미리 1234567을 나눈 나머지를 push한다
    }

    return fib[n];
}

전에 같은 피보나치수열 문제가 있었다.

 

3. 알아야할 사항

  1) 경우의수 접근법

  2) 솔직히 눈치 좀만 빨랐으면 피보나치 걍 알았는데 ㄲㅂ