[programmers] 멀리뛰기

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

코딩테스트 연습 - 멀리 뛰기

• 이 문제는 백준에서 풀었었던 계단 오르기와 비슷한 문제라고 생각했고 같은 방식은 DP로 풀기 시작했다.
• 간단하게 점화식을 세울 수 있었고, Bottom-up방식을 사용했고 2차원DP배열에 메모이제이션으로 구현했다.

# 이문제는 dp문제이다.

def solution(n):
    answer = 0
    dp =[[0]*2000 for _ in range(2)]
    ans = [0 for _ in range(2000)]
    dp[0][0] = 1
    dp[1][0] = 0
    dp[0][1] = 1
    dp[1][1] = 1
    for i in range(2,n+1):
        dp[0][i] = 1
        dp[1][i] = dp[1][i-1]+dp[1][i-2] + 1
    
    return (dp[0][n-1] + dp[1][n-1]) % 1234567


print(solution(5))