문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Ploblem

계단을 오르고 있다. 꼭대기에 도달하려면 n단을 올라야 한다.
매번 1단 또는 2단을 오를 수 있다. 꼭대기까지 오르는데 서로 다른 방법의 수는 몇가지인가?

Example

#1
Input: n = 2
Output: 2
Explanation: 꼭대기까지 오르는데 2가지 방법이 있다.
1. 1 step + 1 step
2. 2 steps

#2
Input: n = 3
Output: 3
Explanation: 꼭대기까지 오르는데 3가지 방법이 있다.
1. 1 step + 1 step + 1step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints

• 1 <= n <= 45

Solved

예를 보면, 피보나치 수열이 생각난다. 그래서 n = 4일 때, 경우를 생각했다.

Input: n = 4
1. 1 step + 1 step + 1 step + 1 step
2. 1 step + 1 step + 2 steps
3. 1 step + 2 steps + 1 step
4. 2 steps + 1 steps + 1 step
5. 2 steps + 2 steps

n = 4이면, n = 2일 때와 n = 3일 때의 결과의 합(2 + 3)과 같다. 피보나치와 비슷하게 흘러가게 됐다.

피보나치와 비슷한 과정을 거치기 때문에 코드를 작성해보자.
먼저 정수 배열 arr을 선언하고, 배열은 n + 2로 생성한다.
그리고 arr의 0, 1, 2 인자에 각각 0, 1, 2를 할당한다.

public int climbStairs(int n) {
  int[] arr = new int[n + 2];
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;
}

피보나치 문제를 풀때는 0, 1, 1, 2, 3... 이렇게 시작하지만, 이번 문제에서는 하나가 빠진다. 그리고 n + 2를 한 이유는 초기값을 넣어줄 때, n = 1이면 이후 값을 못 넣기때문이다.

그리고 반복문을 통해 값을 채워 넣는다.

for(int i = 3; i < n + 1; i++) {
  arr[i] = arr[i - 2] + arr[i - 1];
}

마지막으로 arr[n]을 반환한다.

return arr[n];

All Code

class Solution {
    public int climbStairs(int n) {
        int[] arr = new int[n + 2];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;

        for(int i = 3; i < n + 1; i++){
            arr[i] = arr[i - 2] + arr[i - 1];
        }

        return arr[n];
    }
}