멀리 뛰기

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

핵심 아이디어

어떻게 풀어야하나 고민하다가, DP가 생각났다. DP란 작은 문제에 대한 결과값으로 큰 문제를 해결하는 기법이다. DP를 사용하는 이유는 알고리즘 계산에서 효율성 때문이다. 보통 재귀를 사용하게 되면 같은 로직을 여러번 반복하기 때문에 비효율적인 계산이 될 확률이 높다. 하지만 DP를 사용할 경우 이미 구해놓은 결과값을 불러와서 사용하기 때문에 훨씬 효율적인 연산이 가능하다. 

코드 구현

def solution(n):
    answer = 0
    #print(5%1234567)
    dp = [0] * 20001 # 각 칸마다 도달할 수 있는 방법의 수를 저장하는 DP 테이블 초기화
    dp[1] = 1 # 1가지
    dp[2] = 2 # 2가지
    for i in range(3, n+1):
        # 조건에 맞게 1234567로 나눈 나머지를 dp 테이블에 저장한다. 
        dp[i] = (dp[i-1]+dp[i-2])%1234567
    
    return dp[n] # 결과값 출력