[Python][프로그래머스 Lv.2] 멀리 뛰기

멀리 뛰기

def solution(n):
    answer = 1
    if n % 2 == 0:
        answer = 2
        for i in range(1, n//2):
            answer += fact(n-i) // (fact(i) * fact(n-2*i))
    else:
        for i in range(1, n//2+1):
            answer += fact(n-i) // (fact(i) * fact(n-2*i))
    return answer % 1234567

def fact(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

n = 4일 때, 경우의 수 5
1111
2111 1211 1121 1112 -> 4! / (1! * 3!)
2211

같은 것이 있는 순열을 계산하는 문제라고 생각하고 풀었는데
너무 수학적으로 생각한 것 같다.
math 라이브러리에 factorial 함수가 있는 건 알고 있는데 직접 구현하고 싶어 직접 함수를 만들었다.

다른 사람의 풀이

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

피보나치 수열을 이용한 풀이이다.

n = 1일 때, 경우의 수 1
n = 2일 때, 경우의 수 2
n = 3일 때, 경우의 수 3
n = 4일 때, 경우의 수 5
n = 5일 때, 경우의 수 8
...

def jumpCase(num):
    return (jumpCase(num-1) + jumpCase(num-2)) if num > 2 else num

피보나치 수열을 계산하기 위해 재귀함수를 사용하였다.
num이 커질수록 시간이 기하급수적으로 늘어나므로 위의 풀이가 더 좋은 것 같다.