[leetcode] 70. Climbing Stairs - C

• 분류 - 재귀
• 난이도 - Easy

---

문제 설명

(n층의 계단을 오르는 방법의 수)는 (n-1층을 오르는 방법의 수 + n-2층을 오르는 방법의 수)와 같다.

예를 들어, 4층을 오른다고 하면 3층까지 오르는 경우의 수를 먼저 구하고, 3층을 계단 한 층으로 생각하여 계단 두 층을 오르는 경우의 수를 더하면 되는 것이다.

---

답안 코드 1. 재귀 연산

메모리: 5.4 MB , 시간: 2 ms

int climbStairs(int n){
    int a=0, b=1, c; # 0층을 오르는 방법의 수, 1층을 오르는 방법의 수, n층을 오르는 방법의 수
    
    for(int i=0;i<n;i++){
        c=a+b; // f(n) = f(n-2) + f(n-1)
        a=b; // f(n-2)
        b=c; // f(n-1)
    }
    
    return c;
}

 

재귀의 개념은 알지만 재귀함수는 아직 익숙하지 않아 어려운 것 같다. 추후 재귀함수로도 구현해볼 예정