[Python] 코드업 2641 : 숏다리의 계단 오르기 (Small) 풀이

https://codeup.kr/problem.php?id=2641

 

재귀를 이용해서 한꺼번에 오르는 경우의 수를 모두 따져주었다.

3칸을 한번에 오르는 경우 2번까지 1, 2칸 밖에 못 오르는 것을 체크해주기 위해 check3 변수를 넘겨주었다.

# Codeup #2641 for Search
# https://codeup.kr/problem.php?id=2641

n = int(input())

result = 0

def count_stair(total, check3) : #{
    global result

    check3 -= 1 

    if   n == 0 : return 0

    if n - total >= 1 : count_stair(total+1, check3)  
    if n - total >= 2 : count_stair(total+2, check3)
    if n - total >= 3 and check3 <= 0: count_stair(total+3, 3)
    
    elif total == n : result += 1
#}

count_stair(0, 0)

print(result)