[코테] DP - 멀리 뛰기[프로그래머스]

문제

출처: 프로그래머스 - 멀리 뛰기

풀이

DP를 해결할 때 크게 Botton-up 방식과 Top-down 방식이 있다.
해당 문제는 Top-Down으로 해결하기에는 1 혹은 2로만 움직이기에 2000까지는 너무 깊게 내려가야 하기에 재귀를 쓰게 된다면 시간 초과에 걸릴 확률이 높다. 2칸을 기준으로 잡더라도 깊이가 1000까지 내려가야 하고 트리 구조에서 엣지컷(불필요한 연산 구간 끊기)을 하더라도 최대 2000까지 구하는 깊이까지 내려가야 하기에 어려워 보인다.
그래서 Botton-up 방식으로 해결하는 것이 더 좋아 보인다. 피보나치 수열을 생각해보면 그것과 해결방법이 똑같다는 것을 알 수 있다.
길이 n까지의 리스트를 생성한 후, n이 가장 작은 수부터 직관적으로 구할 수 있는 답을 dp리스트에 업데이트 한다.
직관적으로 구한 다음 수부터 반복문을 이용하여 리스트를 업데이트 하는데, 그 업데이트의 점화식은 피보나치 수열을 구할 때와 같이 구하려는 리스트의 인덱스 값은 -1 이전값과 -2 이전값의 합으로 구하면 된다.

코드

def solution(n):
    if n == 1 or n == 2: # 직관적으로 알 수 있는 값이라면 바로 반환하도록 한다.
        return n

    dp = [0] * (n + 1) # n까지 구해야 하므로 n + 1
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[-1] % 1234567