Leetcode 70. 계단 오르기(Climbing Stairs)

문제 설명

주어진 계단의 수 n에 대해, 한 번에 1계단 또는 2계단을 오를 수 있을 때 계단을 올라가는 방법의 수를 구하는 문제입니다.

예를 들어:

• 계단이 2개라면:
  • 가능한 방법: [1+1], [2] → 총 2가지
• 계단이 3개라면:
  • 가능한 방법: [1+1+1], [1+2], [2+1] → 총 3가지

---

풀이 접근 방법

이 문제는 작은 문제를 해결하며 답을 확장해 나가는 **Dynamic Programming(DP)**의 핵심 원리를 활용합니다.

아이디어

1. 계단 i에 도달하려면:
   • 바로 전 계단 i-1에서 1계단 올라오거나,
   • 두 칸 아래 계단 i-2에서 2계단 올라오는 방법이 있습니다.
2. 따라서, 점화식은 다음과 같습니다:dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2]
   • dp[i]는 계단 i까지 올라가는 방법의 수를 의미합니다.
3. 초기값:
   • dp[0] = 1: 계단이 없으면 올라갈 방법은 1가지(그냥 아무것도 안 하기).
   • dp[1] = 1: 계단 1개일 때 올라가는 방법은 1가지.

---

코드 구현

class Solution {
    public int climbStairs(int n) {
        // 초기화
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;


// 범위 처리
        if(n == 0 || n== 1 ) return 1;

        // 다이나믹
        for(int i = 2 ; i <= n ; i ++) {
            //  ex n=3, 2층까지 올라가는 수 + 1층 올라가는 수
            dp[i] = dp[i -1] + dp[i - 2];
            
        }
        return dp[n];

}

 

---

예제: 계단이 4개라면

초기화

• dp[0] = 1 (방법: 아무것도 안 하기)
• dp[1] = 1 (방법: 1계단)

계산 과정

1. i = 2:
   • dp[2] = dp[1] + dp[0] = 1 + 1 = 2
   • 방법: [1+1], [2] → 총 2가지
2. i = 3:
   • dp[3] = dp[2] + dp[1] = 2 + 1 = 3
   • 방법: [1+1+1], [1+2], [2+1] → 총 3가지
3. i = 4:
   • dp[4] = dp[3] + dp[2] = 3 + 2 = 5
   • 방법: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2] → 총 5가지

결과

• 최종적으로, dp[4] = 5.
• 계단 4개를 올라가는 방법은 총 5가지입니다.

---

최적화 가능성

위 코드는 O(n)O(n)O(n)의 시간 복잡도와 O(n)O(n)O(n)의 공간 복잡도를 가집니다. 하지만 공간 복잡도를 줄이려면, 배열 대신 두 개의 변수만 사용할 수도 있습니다.

최적화된 코드:

class Solution {
    public int climbStairs(int n) {
        // 초기화
        int prev1=1, prev2 = 1;
        int current = 0;


// 범위 처리
        if(n == 0 || n== 1 ) return 1;
…     
    }
}

• 이 코드는 공간 복잡도를 O(1)O(1)O(1)로 줄여줍니다.