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

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

프로그래머스

 

코드

시간초과 발생

from itertools import combinations
def solution(n):
    answer = 1
    b = 1
    if n % 2 == 0 : 
        while n > 2*b:
            answer += len(list(combinations(range(n-b), b)))
            b += 1
        answer += 1
    else:
        while n >= 2*b:
            answer += len(list(combinations(range(n-b), b)))
            b += 1
            if n < 2*b: break
    return answer

 

재귀를 이용한 풀이 (피보나치)

import sys
sys.setrecursionlimit(10**7)

memo=[1,1]

def solution(n):
    if len(memo)-1>=n:
        return memo[n]
    else:
        memo.append(solution(n-1)+solution(n-2))

    return memo[n]%1234567

 

피보나치

def solution(n):
    a, b = 1, 2
    for i in range(2,n):
        a, b = b, a+b
    return b

 

문제보면 조합밖에 생각안나던데 피보나치는 어떻게 생각해내신거지 

..

갈길이 멀다 멀어 ..!>!>