멀리 뛰기

 

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

프로그래머스

문제풀이

효진이가 n칸을 뛰어야 할 때, n-1칸에서 1칸을 뛰거나, n-2칸에서 2칸을 뛰는 두 가지 선택이 가능하다. 이것은 점화식으로 구현 할 수 있다. 123567로 정수를 나누는 작업을 하기 때문에 테스트 케이스가 널널해서 굳이 DP를 사용하지 않아도 시간 초과는 나지 않을거다.

 

라이브러리 중에 lru_cache라는 라이브러리를 알게 되어서 사용하게 되었다. 메모제이션을 아주 간단하게 구현이 가능해진다.

• 함수의 인자는 불변 해야함
• maxsize로 캐시 크기를 제한가능 None이라면 무제한
• 함수의 결과를 캐시에 저장하고, 동일한 인자로 함수가 호출될 때 이전에 계산한 결과를 반환

from functools import lru_cache
import sys

sys.setrecursionlimit(10000000)


@lru_cache(maxsize=None)
def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return (solution(n - 1) + solution(n - 2)) % 1234567

 

 

Bottom UP 방식으로 풀이 하면 아래와 같다.

def solution(n):
    dp = [0] * (n + 2)

    dp[1] = 1
    dp[2] = 2

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