[프로그래머스 / 파이썬 풀이] 멀리 뛰기

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

dp문제 중 하나

n개의 칸을 뛰려면 n-1개 칸을 뛸 때의 경우의 수 + n-2개 칸을 뛸 때의 경우의 수가 돼야 한다.

(5개의 칸 = 4개의 칸 + 3개의 칸 .... 3개의 칸 = 2개의 칸 + 1개의 칸) 과 같은 식으로 결론적으론 피보나치 수열과 같은 방식의 풀이로 풀이하게 된다.

 

memo 배열을 초기화 하는 방법 중 n+1로 둔 이유는 만약 n이 1이 들어오게 된다면 3번째 인덱스인 memo[2] 를 생성할 수 없기 때문에 그 부분을 고려해여 n+1로 두게 된다.