[99클럽 코딩 스터디 8일차 TIL] LeetCode 70. Climbing Stairs 해설 및 풀이 (Java)

 

99클럽 코딩 스터디 8일차 TIL

LeetCode 70. Climbing Stairs

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

---

 

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
 

Constraints:

1 <= n <= 45

 

한글 해석

 

당신은 계단을 오르고 있습니다. n꼭대기에 도달하려면 단계가 필요합니다.

매번 당신은 오르 1거나 2계단을 오를 수 있습니다. 정상까지 올라갈 수 있는 뚜렷한 방법은 몇 가지입니까?

 

예시 1:

입력: n = 2
 출력: 2
 설명: 정상에 오르는 방법은 두 가지가 있습니다.
1. 1걸음 + 1걸음
2. 2단계

예시 2:

입력: n = 3
 출력: 3
 설명: 정상에 오르는 방법은 세 가지가 있습니다.
1. 1걸음 + 1걸음 + 1걸음
2. 1걸음 + 2걸음
3. 2걸음 + 1걸음
 

제약사항:

1 <= n <= 45

 

---

문제 유형

 

수학
동적 프로그래밍
메모이제이션

 

풀이 방법 도출

 

이 문제는 일종의 피보나치 문제입니다.

 

1. 계단의 꼭대기까지 오르는 방법의 수는 마지막 계단에 오르기 직전의 1칸 전(n-1) 혹은 2칸 전(n-2)에서 올라오는 두 가지 방법이 있습니다.
2. 따라서, f(n) = f(n-1) + f(n-2)가 됩니다.
3. 예를 들면 n = 1일 때는 방법 1개, n = 2일 때는 방법 2개, n = 3일 때는 f(3) = f(2) + f(1) = 2 + 1 = 3입니다.
4. 이 규칙을 토대로 점화식을 이용해서 반복문으로 계산할 수 있습니다.

 

시간 복잡도

• 반복문 사용으로 O(N)

 

공간 복잡도

• 배열 및 리스트를 사용하지 않고 3개의 변수로만 해결하기 때문에 O(1)

 

---

 

핵심 코드 삽입 및 설명

 

class Solution {
    public int climbStairs(int n) {
        // n이 1 또는 2일 경우는 직접 반환
        if (n <= 2) return n;

        // 피보나치 초기값 설정
        // f(1) = 1, f(2) = 2
        int first = 1;   // f(n-2)
        int second = 2;  // f(n-1)
        int third = 0;   // f(n)

        // 3부터 n까지 반복해서 f(n) 계산
        for (int i = 3; i <= n; i++) {
            third = first + second; // f(n) = f(n-1) + f(n-2)
            first = second;         // 다음 루프를 위해 업데이트
            second = third;
        }

        // 최종 결과 반환 (f(n))
        return third;
    }
}