99클럽 코테 스터디 6일차 TIL + 수열(

70. Climbing Stairs

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

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

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

 

---

 

음 생각해보자

n이 2일 때 방법이 2가지

n이 3일 때 방법이 3가지 

n이 4일 때 방법이 5가지 

 

n이 5일 때 방법이 8가지?

11111
1112
2111
221
122
212
1211
1121

 

n이 6일 때 방법이 13가지 

....

 

규칙을 잘 모르겠는데

 

 

 

! 알고리즘을 생각해보자

 

-> 피보나치 수열을 사용하면 되겠다.

 

n 이 1이나 2일 때는 각각 1, 2 이므로 n이 3일 때부터를 고려하면 된다. 

 

 

 

 

 

1) 전체 코드

class Solution {
    public int climbStairs(int n) {

        int a = 1; //f(n-2)
        int b = 2; //f(n-1)

        if (n <= 2){
            return n;
        }

        for(int i=3; i<=n; i++){
            int temp = b;
            b = a+b;
            a = temp;
        }
        
        return b;
        
    }
}

 

 

- a를 f(n-2) 즉, 이전의 이전 단계로 생각하고 b를 f(n-1) 이전 단계로 생각하면 된다. 

 

b = a+b는 f(n) = f(n-2) + f(n-1)

a = temp는 이전의 이전 단계에 다음 연산을 위해 이전 단계의 값을 넣어준다.

 

 

---

피보나치 수열을 이론으로만 배워서 코드를 풀 줄만 알았지 직접 문제 해결을 위한 피보나치 수열을 사용해 보는 것은 처음이다.

이러한 재귀 문제가 나올 때 피보나치 수열을 사용해서 문제를 풀어나가야겠다.