1. 문제 설명

멀리 뛰기

2. 문제 분석

1칸 또는 2칸을 뛸 수 있다. 총 n칸을 뛸 수 있는 경우의 수를 구한다.

• 1칸, 2칸을 아무런 조건 없이 마음대로 선택해 뛸 수 있기 때문에, 1칸 전/2칸 전 사용했던 경우의 수를 그대로 활용할 수 있다. 이를 활용해 dp를 사용한다.
• 조합 수식을 사용할 수도 있다. 위 문제는 1과 2를 마음대로 사용해 총합 n을 구하는 문제이다.

예를 들어 n=5를 1과 2를 사용한 조합으로 풀어 보자. 관건은 2를 몇 번 사용할 수 있느냐를 확인하는 데 있다.

1. 1을 5개 2를 0개 사용: 5C0
2. 1을 3개 2를 1개 사용: 4C1
3. 1을 1개 2를 2개 사용: 3C2

총합이 곧 n을 구하는 데 있어 사용되는 1과 2의 경우의 수이고, 수식으로 표현하면 nC0 + (n-1)C1 + ... (n-n//2)C(n//2)이다.

3. 나의 풀이

def solution(n):

    # 1. dp로 풀기
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = (dp[i-1] + dp[i-2])%1234567
        # 2칸을 쓸 수 있을 때 1칸 이전, 2칸 이전 정보를 활용
    return dp[n]

def solution(n):

    # 2. n 수식 구하기
    # result = nC0 + (n-1)C1 + ... (n-n//2)C(n//2)

    half_n = n//2
    total = 0

    def get_comb(n, k):
        if k == 0: return 1
        if n == k: return 1
        k = min(k, n-k)
        up = 1
        down = 1

        for i in range(n-k+1, n+1):
            up *= i
        for i in range(1, k+1):
            down *= i
        return up//down


    for i in range(half_n+1):
        total += get_comb(n-i, i)