[프로그래머스/Python] 멀리 뛰기

문제 설명

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

문제 풀이

1. 입력값으로 n개의 칸이 주어질 때,

   1. 만약 n이 2보다 작거나 같다면 n 그대로 반환

   2. n이 2보다 크다면

      1. 0으로 초기화된 dp 리스트 생성, dp[1] = 1, dp[2] = 2이며

      2. 3부터 n까지 순회

         1. dp[n]는 dp[n-1]과 dp[n-2]를 더한 값이다. 즉, 현재까지의 칸 수에 도달하는 방법의 수는 바로 이전 칸까지 도달하는 방법의 수 + 그 이전 칸까지 도달하는 방법의 수를 더하면 현재 칸 까지 도달하는 방법의 수가 나온다.

         2. 1234567로 나눈 나머지를 저장한다

      3. n칸까지 도달하는 멀리뛰기 방법의 수 dp[n]을 반환한다.