82. 멀리 뛰기

[문제]

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

프로그래머스

 

 

[풀이]

1. 문제의 답에는 피보나치 수열의 규칙이 있음

2. 피보나치 수열을 구현하면 되는데, 재귀함수로 구현할 때는 그 과정에서 메모이제이션을 통해 시간복잡도 최적화

3. 구현할 때 n-2를 먼저 할 것

 

재귀함수로 구현

def solution(n):
    memo = {1:1, 2:2}
    return pibo(n, memo) % 1234567

def pibo(n, memo):
    
    if n in memo:
        return memo[n]

    memo[n] = (pibo(n - 2, memo) + pibo(n - 1, memo))
    return memo[n]

 

for 문으로 구현

def solution(n):
    if n == 1:
        return 1 % 1234567
    elif n == 2:
        return 2 % 1234567
    else:
        a,b = 1,2
        for i in range(n-2):
            a, b  = b, a+b
        return b % 1234567