[프로그래머스] Lv3 멀리 뛰기

링크: 연습 문제 > 멀리 뛰기

---

코드

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

---

풀이

dp	건너는 방법	방법 수
dp[1]	[1]	1
dp[2]	[2], [1, 1]	2
dp[3]	[2, 1], [1, 2], [1, 1, 1]	3
dp[4]	[2, 2], [2, 1, 1], [1, 1, 2], [1, 2, 1], [1, 1, 1, 1]	5
dp[5]	[1, 1, 1, 1, 1], [1, ,1 ,1, 2], [1,1, 2, 1], [1,2, 1, 1], [2, 1, 1, 1],[2, 2, 1], [1, 2, 2], [2, 1, 2]	8

• 건너는 방법 수는 dp[i] = dp[i-2] + dp[i-1]식으로 구해진다.

테스트케이스 1번에서 런타임 에러가 났었는데 n이 1일 경우 n[2]에 값을 할당해서 그랬다.