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

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

프로그래머스

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한사항

n은 1 이상, 2000 이하인 정수입니다.

풀이 설계

• 이번 dp는 dp[i] = dp[i-2] + dp[i-1] 이라는 점화식을 가지고 있다.
• n이 1이나 2일 경우를 미리 저장하고 dp를 채운다.

1차 시도 (런타임에러)

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

2차 시도 (성공)

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

후기

• 찾아보니 이런 점화식을 가지고 피보나치 수열이라고 한다.
• 1차 시도에서 테스트 케이스 1개가 계속 런타임에러가 떴는데 알고보니 만약 n이 1이라면 dp배열이 1까지만 생성되어 dp[2]를 저장할 수 없기 때문이었다.