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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12914

기존에 dp로 풀었던 동전던지기 등과 매우 비슷한 유형의 문제다.

한 칸의 경우 한칸, 두 칸의 경우 (1,1),(2), 3칸의 경우
1)한 칸을 뛴 경우에서 두 칸을 더 뜀,
(1,2)
2)두칸을 뛴 경우에서 한 칸을 더 뜀
(1,1,1), (2,1)

....

n칸을 뛴 경우의 수

• n-2 칸을 뛴 후에 + 2칸을 더 뛴다.
• n-1 칸을 뛴 후에 + 1칸을 더 뛴다.

이런 원리를 이용해서 풀어보면 된다.

def solution(n):
    answer = 0
    
    if n == 1 :
        return 1 
    else:
        dp=[0] * (n+1)
        dp[1] = 1 #한 칸의 경우 한칸
        dp[2] =2 
        for i in range(3,n+1):
            dp[i] = (dp[i-2] + dp[i-1]) % 1234567
        
    return dp[-1]