멀리 뛰기

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.

나의 풀이

import math

def jumpCase(num):
    return sum([math.factorial(num-i)/(math.factorial(i)*math.factorial(num - (2*i))) for i in range(num //2+1)])

같은 것을 포함한 순열의 수로 풀었다.

n개 중에 같은 것이 a개, b개, c개 있을 때 순열의 수: n!/a!b!c!

n이 4이라 가정했을 때 (1, 1, 1, 1), (1, 1 ,2), (2, 2)의 각각 모든 순열을 합한 값이 모든 경우의 수이다.

2칸 뛸 수 있는 최대의 수(num//2 + 1)까지

num-i : 총 n개 나누기

i: 2칸 뛰는 횟수

num - (2*i): 1칸 뛰는 횟수

다른풀이

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

그런데 이렇게 쉬운 풀이가 있었다. ㅠㅠ

n칸 일 때 (n-2) + (n-1)의 경우의 수의 합으로 풀 수 있다.