문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다.
효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

문제 접근 방식

n과 같이 변수의 조건의 범위가 크거나 1234567와 같이 결과값이 커서 나머지를 출력하라는 문제 거의 대부분은 DP 문제 입니다.
일반적인 완전 탐색의 접근법으로는 시간 초과가 나서 테스트 케이스를 전부 통과할 수 없습니다.

따라서, 멀리 뛰기 문제도 DP로 접근했고 주어진 테스트 케이스에 대해서 규칙을 찾아보았습니다.

• n=1일 때, 1가지
• n=2일 때, 2가지
• n=3일 때, 3가지
• n=4일 때, 5가지

규칙이 무엇인지 보이시나요?!

이 문제는 피보나치 수열을 구하는 문제와 동일합니다.

점화식으로 표현하면 다음과 같습니다.

DP(N) = DP(N-1) + DP(N-2)

풀이 코드

def solution(n):
    memo = [-1 for _ in range(2001)]

    def dp(x):
        if memo[x] != -1: return memo[x]
        if x == 1: return 1
        if x == 2: return 2
        memo[x] = (dp(x-2) + dp(x-1)) % 1234567
        return memo[x]
    return dp(n)