하드러너 블레이크 (Hard-Learner Blake)

• 문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.

• 답안

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

• 이 문제 키워드
  • 피보나치로 해결. 재귀를 사용하면 시간효율성 낮고, depth 조절을 해야된다. DP로 하면 반복 범위가 정해지는 효과
  • 피보나치를 판단하는 방법은 각 경우를 계산해서 1, 2, 3, 5, 8, 13,,,, 해보니 피보나치! 이게 아님
  • 5칸의 경우: * -> 점프를 의미
    • Case 1: * * * * / *       4번째 점프까지하고 1칸 건너는 한가지 경우 (n-1)항 경우의수 x 1
    • Case 2: * * * / * *       3번째 점프까지하고 2칸 건너는 한가지 경우 (n-2)항 경우의수 x 1 
    • 그래서 5번째 칸까지 건너는 경우의 수가 (n-1)항 경우의수x1 + (n-2)항 경우의수x1 이 된 것! -> 피보나치
  • 다만, for i in range(3, n+3): 처럼 범위 지정할 때, 시작점이 끝점보다 작은지 꼭 확인하자.