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

문제

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

풀이

멀리 뛰기 칸이 1개 일때부터 조합의 수를 나열해보자.

1 -- [1] -- 1
2 -- [1,1][2] -- 2
3 -- [1,1,1][1,2][2,1] -- 3
4 -- [1,1,1,1][1,1,2][1,2,1][2,1,1][2,2] -- 5

눈치 빠른 사람은 여기서 이미 눈치챘겠지?
바보같은 나는 6까지 나열하고서야 눈치챘다.

def solution(n):
    jump = {0:1, 1:1}
    for i in range(2, n+1):
        jump[i] = jump[i-2] + jump[i-1]
    return jump[n] % 1234567

LEVEL 2까지는 그림이나 예시를 보면서 머리를 굴리면 쉽게 답을 찾을 수 있는데
LEVEL 3부터는 수학적 센스를 많이 요구하는 것 같다.
규칙을 빨리 찾아내면 쉽게 풀지만, 규칙을 못 찾으면 무한하게 헤매게 된다.

규칙 찾는데 50분, 코드 작성은 5분.