10-2) 돌다리 건너기

김예지·2021년 9월 8일

[알고리즘] javascript 인프런 강의

목록 보기

88/91

문제

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?

[입력설명]
첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다.
[출력설명]
첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.

입력예제 1

출력예제 1

문제 풀이

앞의 문제와 거의 동일한 유형이다. 다만, 돌다리 건너기는 도착지가 dy[n+1]인것을 기억하자! 돌다리를 건넌다고 끝이아니라, 철수가 땅에 도착해야 하기 때문에 이를 고려해야하는 것이다. (돌다리+땅(도착지))

코드

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(n){  
                let answer;
                let dy=Array.from({length:n+2}, ()=>0);
                dy[1]=1;
                dy[2]=2;
                for(let i=3; i<=n+1; i++){
                    dy[i]=dy[i-2]+dy[i-1];
                }
                answer=dy[n+1];
                return answer;
            }

            console.log(solution(7));
        </script>
    </body>
</html>