재귀로 계단 오르기 경우의 수

LEARNING GUIDE

📖 학습 내용

학습 내용

계단 수 n이 입력됩니다. 한 번에 1칸 또는 2칸을 오를 수 있을 때 n개의 계단을 오르는 경우의 수를 메모이제이션 재귀로 출력하세요.

📥 테스트 입력값

🔎 실행 결과

💡 힌트 코치

stairs(n) = stairs(n-1) + stairs(n-2), 기저 조건: stairs(1)=1, stairs(2)=2 입니다.

✅ 정답 공개

memo = {}
def stairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n in memo:
        return memo[n]
    memo[n] = stairs(n-1) + stairs(n-2)
    return memo[n]

print(stairs(int(input())))

◀ 이전 목록 다음 ▶