CYMAKR

helloworld 33.멀리뛰기 본문

기술노트/알고리즘

helloworld 33.멀리뛰기

싀마 2017.04.14 17:24

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)

(1칸, 2칸, 1칸)

(1칸, 1칸, 2칸)

(2칸, 1칸, 1칸)

(2칸, 2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.


1일 경우 -> ["1"] 1가지

2일 경우 -> ["1,1","2"] 2가지

3일 경우 -> ["1,2","1,1,1","2,1"] 3가지

4일 경우 -> ["1,1,1,1","1,1,2","1,2,1","2,1,1","2,2"] 5가지

5일 경우 -> ["1,1,1,1,1","2,1,1,1","1,2,1,1","1,1,2,1","1,1,1,2","2,2,1","2,1,2","1,2,2"] 8가지


1, 2, 3, 5, 8... => 피보나치 수열


피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다.


n = 0, 1,...에 해당하는 피보나치 수는 (OEIS의 수열 A000045)

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946... 이다. 


구현


function jumpCase(num) {

var answer = 0;

  var fibo1 = 1, fibo2 = 1;


  for (var i=1; i<num; i++) {

    answer = fibo1 + fibo2;

    fibo1 = fibo2;

    fibo2 = answer;

  }


return answer;


'기술노트 > 알고리즘' 카테고리의 다른 글

helloworld 33.멀리뛰기  (0) 2017.04.14
0 Comments
댓글쓰기 폼