[LeetCode C++] 70. Climbing Stairs

⭐️ 난이도

 

Easy

 

---

⭐️ 문제

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

You are climbing a staircase. It takes n steps to reach the top.

당신은 계단을 오르고 있다. 계단을 모두 오르기까지는 총 n개의 계단을 올라야 한다.

 

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

한 번에 1 or 2개의 계단을 오를 수 있다. 계단을 모두 오르기까지 가능한 방법은 몇 개가 있겠는가?

 

단, n의 범위는 (1 <= n <= 45)이다.

---

⭐️ Follow-up

 

X

 

---

⭐️ Idea flow

 

이 문제의 핵심은 결국 1와 2만을 이용하여 정수 n을 만드는 방법의 수를 세는 것이다.

(단 순서가 바뀌면 다른 방법으로 판단한다.)

 

딱히 발견할 수 있는 규칙이 없기 때문에, n이 1일 때부터 6일 때까지 하나씩 직접 모든 경우의 수를 세어보았다.

n이 1일 때, 1 (1)

n이 2일 때, 2 (1+1, 2)

n이 3일 때, 3 (1+1+1, 1+2, 2+1)

n이 4일 때, 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

n이 5일 때, 8 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 2+2+1, 2+1+2, 1+2+2)

n이 6일 때, 13

 

n이 4일 때까지만 해봐도 대충 감이 오는데 확실하게 하기 위해서 n이 6일 때까지 해보았다.

 

규칙은 바로 F(n) = F(n - 1) + F(n - 2)였다.

피보나치와 같은 규칙을 가지고 있다.

 

 

---

⭐️ Code

class Solution {
private:
    vector<int> dp;
public:
    int climbStairs(int n) {
        if(n == 1)  return 1;
        if(n == 2)  return 2;
        
        dp.assign(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

 

 

---

⭐️ Feedback

 

내가 짠 코드의 경우에는 Time Complexity가 O(n), Space Complexity가 O(n)이다.

하지만 다른 사람의 코드를 둘러보다 Space complexity를 O(1)로 줄인 코드를 발견했다.

 

구한 값을 따로 담아둘 컨테이너(vector<int> dp)를 따로 사용하지 않은 것인데,

prev(바로 이전 수를 담는 변수)와 prev2(두 번째전 수를 담는 변수)를 선언해서 이를 이용했다.

 

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev = 2, prev2 = 1, res;
        for (int i = 3; i <= n; i++) {
            res = prev + prev2;
            prev2 = prev;
            prev = res;
        }
        return res;
    }
};
//https://leetcode.com/problems/climbing-stairs/discuss/1504255/C%2B%2B-Simple-and-Easy-Fibonacci-Solution-With-Explanation