멀리 뛰기

• 피보나치

from functools import reduce
def solution(n):
    return reduce(lambda x, n :[x[1], x[0] + x[1]], range(n), [0, 1])[-1] % 1234567

피보나치

한번에 1 or 2 만큼 움직일 수 있으니 패터을 봅시다. DP[n] : n칸까지 도달할 수 있는 경우의수 라고 정의하겠습니다.

DP[1] = 1

• 한칸뛰기

DP[2] = 2

• 한칸씩 2번뛰기, 2칸 한번에 뛰기

DP[3] = 3

• 2칸뛰는 경우의 수(DP[2]) + 남은 1칸 뛰기, 한칸뛰는 경우의 수(DP[1]) + 남은 2칸 한번에 뛰기

DP[4] = 5

• 3칸뛰는 경우의 수(DP[3]) + 남은 1칸 뛰기, 2칸뛰는 경우의 수(DP[2]) + 남은 2칸 한번에 뛰기

DP[n] = DP[n-1] + DP[n-2]

• n-1칸뛰는 경우의 수(DP[n-1]) + 남은 1칸 뛰기, n-2칸뛰는 경우의 수(DP[n-2]) + 남은 2칸 한번에 뛰기

피보나치 수열이다. reduce를 이용해 한번에 구해주었다.