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

https://school.programmers.co.kr/learn/courses/30/lessons/12914#

프로그래머스

---

보자마자 dp로 풀었는데 제출하고 나서 다른 분들 풀이를 보니까 재귀로 푼 분들이 훨씬 많았다.

 

재귀로도 풀어봤는데 대부분의 테케에서 시간초과가 떴다.

문제 조건이 바뀌었나? 바뀌기 전에는 재귀로 풀어도 통과가 됐었나봄

 

 

제출 코드 (dp)

def solution(n):
    dp = [0]*n
    dp[0] = 1 #1칸
    if n >= 2:
        dp[1] = 2 #1칸 또는 2칸
        for i in range(2,n):
            dp[i] = dp[i-2]%1234567 + dp[i-1]%1234567
    return dp[n-1]%1234567