[Lv.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이 1부터 7까지 한 번 나열해봤다.

• n = 1 -> result = 1
• n = 2 -> result = 2
• n = 3 -> result = 3
• n = 4 -> result = 5
• n = 5 -> result = 8
• n = 6 -> result = 13
• n = 7 -> result = 21

result의 값들이 뭔가 어디서 본 값들 아닌가?

그렇다. 맨 앞에 1만 더 추가하면 피보나치 수열과 같다.

이것만 알면 끝이다...ㅋㅋㅋㅋㅋㅋ

통과 코드

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