[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 이하인 정수입니다.

 

입출력 예

n	result
4	5
3	3

 

문제 풀이 순서

이거 뭔가 공부한 느낌인데 코드로 어떻게 구현하지? 라고 생각되었다. 

피보나치 수열 느낌이라 재귀적으로 풀었는데 오류가 떴다... 시간 이슈...!

그러므로 우리는 DP를 사용할 것이다.
참고로 DP에서는 "규칙을 찾아 내가 표를 완성해 나간다!"라고 생각하자!!

 

ex) n = 4

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]
n은 1 이상으로 무시	0	0	0	0

↓

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]
	1	2	1 + 2 = 3	2 + 3 = 5

 

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2])
    
    return dp[n] % 1234567