[프로그래머스(파이썬/Python)] 멀리 뛰기

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

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

 

프로그래머스 Level3 문제치고 정말 쉬운 DP문제입니다.

 

DP 문제인 정당성은 N칸을 점프하는 경우의 수가 그 이전 칸(N-1, N-2)의 경우의 수에서 더해지는 방식이기 때문에 전체 문제의 최적해가 부분 문제의 최적해를 보장한다는 점에 있죠.

 

N번째 칸에 도착하기 위해서는 N-1번째 칸에서 1칸 점프를 하거나, N-2번째 칸에서 2칸 점프를 하면 됩니다. N-3번째 칸 이전에서는  점프하는 동안 무조건 N-1번째 칸, N-2번째 칸을 거쳐야 하기 때문에 고려하지 않아도 되죠.

 

따라서 점화식은 피보나치 수열을 따르게 되며 풀이는 아래와 같습니다.

 

[풀이]

def solution(n):
    dp = [0] * (n+1)

    # 1칸 전에서 1칸을 점프하는 경우 + 2칸 전에서 2칸을 점프하는 경우의 수
    for i in range(1, n+1):
        if i == 1: dp[i] = 1
        elif i == 2: dp[i] = 2
        else: dp[i] = (dp[i-1] + dp[i-2]) % 1234567

    return dp[n]