99클럽 코테 스터디 22/99일차 TIL #멀리 뛰기(미들러)

'''
경우의 수
한 번에 1칸 또는 2칸
1로 개수 만들고,
2개씩 줄이면서 개수 늘리고
2의 위치 개수

1로 만들어진 숫자 1개
2의 개수 = 0~ n//2개


2의 개수 0개~ n/2

total num = n
2의개수, 1의 개수 =  a, n-

'''

import math

def solution(n):
    total_count = 0
    
    for cnt_2 in range(0, n // 2 + 1):
        cnt_1 = n - 2 * cnt_2
        total_steps = cnt_1 + cnt_2
        
        # 조합의 개수 계산: total_steps! / (cnt_2! * cnt_1!)
        combinations = math.factorial(total_steps) // (math.factorial(cnt_2) * math.factorial(cnt_1))
        
        total_count += combinations
    
    return total_count % 1234567