멀리 뛰기

def solution(n):
    # DP - 한번에 1칸 또는 2칸
    dp = [0 for i in range(n+2)]
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n] % 1234567

• DP 기법으로 간단히 풀 수 있다.
• 최종결과에 도달하기 전, 어떤 상황이 있을 수 있을지 생각해보면 간단하다.
• iteration을 하며 리스트에 저장한 값들을 저장해놓고 필요할 때 다시 계산할 필요없이 쓰면 O(N).
  • Tabulation 기법

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges