[프로그래머스] level 2 멀리 뛰기(JS)

문제 링크 : 코딩테스트 연습>연습문제>멀리 뛰기

---

조건

• 1칸 또는 2칸 뛸 수 있다.
• 멀리뛰기 할 칸의 수 n
• return n까지 가는 경우의 수 % 1234567

패턴

• n = 1 → return 1

  • 1

• n =2 → return 2

  • 1 1
  • 2

• n = 3 → return 3

  • 1 1 1
  • 2 1
  • 1 2

• n = 4 → return 5

  • 1 1 1 1
  • 1 2 1
  • 1 1 2
  • 2 1 1
  • 2 2

• n = 5 → return 8

  • 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

• n = 6 → return 13

  • 1 1 1 1 1 1
  • 2 1 1 1 1
  • 1 2 1 1 1
  • 1 1 2 1 1
  • 1 1 1 2 1
  • 1 1 1 1 2
  • 2 2 1 1
  • 2 1 2 1
  • 2 1 1 2
  • 1 2 2 1
  • 1 2 1 2
  • 1 1 2 2
  • 2 2 2

• 요약하자면 피보나치 수열의 패턴을 가지고 있다.

  n	return
  1	1
  2	2
  3	3
  4	5
  5	8
  6	13

• 피보나치 수열의 공식이 F(n) = F(n-1) + F(n-2) 일때

• F(n) % 1234567 = (F(n-1) + F(n-2)) % 1234567
  = (F(n-1) % 1234567 + F(n-2) % 1234567) % 1234567

코드

function solution(n) {
  let arr = [0, 1]
  for (let i = 1; i <= n; i++) {
    arr.push(arr[arr.length - 1] + arr[arr.length - 1 - 1] % 1234567)
  }
  return arr[arr.length - 1]
}