프로그래머스 - LV.2 - 멀리 뛰기

나의 풀이

def solution(n):
    if n < 3:
        return n 
    #피보나치 수열과 같음
    cnt = [0] * (n+1)
    cnt[1] = 1
    cnt[2] = 2
    for i in range(3 ,n+1):
        cnt[i] = cnt[i-1] + cnt[i-2]
    return cnt[n] % 1234567

문제를 이해하기 위해 종이에 끄적이며 규칙을 파악하려 경우의 수를 구했고
익숙한 피보나치가 떠올라 피보나치 수열로 풀어내었다.
재귀함수 방법으로 풀 경우, 시간 복잡도가 많이 늘어났다.
피보나치 수열을 재귀함수로 구현할 경우 많은 시간이 드는 것은 항상 주의하여야 한다.

다른 풀이

import math

def solution(n):
    answer = 1
    for i in range(1, n):
        num = n - i * 2
        if num >= 0:
            answer += math.comb(num + i, i)
            answer = answer % 1234567
        else:
            break
    return answer

조합까지 생각했던 사람으로 이 풀이는 상당히 재미있는 풀이였다.
python에서 사용할 수 있는 메서드는 알아두는 것은 중요하다