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

문제

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

프로그래머스

 

---

풀이

def solution(n):
    answer = [1,1]
    
    for i in range(2, n+1):  # F(n) = (F(n-1) + F(n-2)) % 1234567
        answer.append((answer[i - 1] + answer[i - 2]) % 1234567)
    return answer[-1]  # 마지막 결과를 return

---

설명

사용할 알고리즘이 정확하게 DP 인지는 몰랐으나 뭔가 형태가 피보나치 수열 인 것 같아서 그렇게 접근했다.

 

다만 문제에서는 초기 조건이 다르다.

 

뛰어야 하는 칸(n) 이 

• 0칸인 경우 -> 1가지
• 1칸인 경우 -> (1칸) -> 1가지
• 2칸인 경우 -> (1칸, 1칸), (2칸) -> 2가지