[Level 3] 멀리 뛰기

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

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

---

접근

시간초과가 날 것 같았지만 백트래킹으로 시도를 해보았다. 역시 시간초과가 발생했다. 그래서 1칸, 2칸까지 뛸 수 있다는 것에 동적계획법이 생각이 났고 점화식을 세우려고 했다.

경우의 수를 봤을 때 f(n) = f(n-1) + f(n-2)라는 점화식을 세울 수 있었고 그대로 구현을 하였다.

 

구현

n은 1이상 2000이하의 수가 들어오기 때문에 1부터 2000의 번호를 갖는 dp라는 리스트를 생성하였고 0으로 초기화하였다. 이후 n=1일 때와 n=2일 때를 먼저 1과 2로 지정한 다음에 n=3 이상일 때만 for문으로 점화식대로 구하였다.

def solution(n):
    answer = 0
    dp = [0 for _ in range(2001)]
    dp[1] = 1
    dp[2] = 2
    if n <=2:
        answer = dp[n]
    else:
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        answer = dp[n]
    return answer%1234567