[프로그래머스] 멀리 뛰기 (파이썬)

🗓️ 문제 설명

• 멀리 뛰기를 할 때, 한번에 1칸 또는 2칸을 뛸 수 있습니다.
• 칸이 총 4개 있을 때, 맨 끝 칸에 도달할 수 있는 방법은 다음과 같습니다.
  • (1칸, 1칸, 1칸, 1칸)
  • (1칸, 2칸, 1칸)
  • (1칸, 1칸, 2칸)
  • (2칸, 1칸, 1칸)
  • (2칸, 2칸)
• 멀리 뛰기에 사용될 칸의 수 n이 주어질 때, 끝에 도달하는 방법이 몇가지인지 알아내 1234567을 나눈 나머지를 반환하세요.
• 제한 사항
  • 1  ≤ n ≤ 2000
• 입출력 예시

n	result
4	5
3	3

 

💻 코드

최종 코드

 

코드 풀이

n길이의 칸을 이동할 수 있는 방법수는 피보나치수열을 통해 구할 수 있습니다.
예를 들면 n=1 일 때는 (1칸)로 1개, n=2일 때는 (1칸, 1칸), (2칸)으로 2개, n=3일 때는 (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸)으로 3개가 됩니다. 이를 리스트로 만들어보면 [1, 2, 3, 5]이 되기 때문에 두번째 값부터 시작하는 피보나치 수열(1, 1, 2, 3, 5)과 동일합니다.