[Leetcode 아주 상세한 문제풀이] 70. Climbing stairs - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 70번 문제 Climbing stairs 다.

우선 문제를 살펴보자.

 

리트코드 70번 문제 Climbing stairs 링크

Climbing Stairs - LeetCode

Climbing Stairs - LeetCode

 

 

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

 

 

문제 설명

문제에 대해 간략히 알아보자.

한 번에 계단을 1칸 혹은 2칸씩 올라갈 수 있다.

이때 주어진 계단 (n)을 끝까지 올라갈 수 있는 경우의 수가 몇가지 인지 구하는 문제다.

예시 2번에서 보는 것처럼 계단 높이가 3일때 3가지 경우의 수가 생긴다.

1칸씩 3번에 걸쳐 올라갈수도 있고, 1칸 먼저 올라간 후 2칸을 올라갈수도 있고, 혹은 2칸 먼저 올라간 후 1칸을 올라갈수도 있다.

문제가 대한 설명이 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

우선 이 문제에 대한 접근 방법을 생각해 보자.

이 문제는 반대로 생각해보면 좋은데 예를 들어 10개의 계단이 있다고 생각해 보자.

문제의 조건에 따라 1칸 혹은 2칸만 움직일 수 있으므로,

10번째 칸에 도달하기 위해서는 8번째 칸에서 2칸을 올라가거나

혹은 9번째 칸에서 1칸을 올라가는 경우의 수가 있다.

즉, 8번재 칸과 9번째 칸에 도달할 수 있는 경우의 수를 합하면 10번째 칸에 도달할 수 있는 경우의 수를 구할 수 있다.

여기서 8번째 칸에서 1칸씩 두번 올라가는 경우는 제외되는데,

그 경우는 9번째 칸에서 1칸 올라가는 경우의 수 안에 포함되기 때문이다.

따라서 이 문제는 dynamic programming을 통해 접근하는 것이 바람직하다고 볼 수 있다.

 

 

문제 풀이

우선 계단 높이를 입력받을 함수를 정의해 준다 (line 1)

만약 계단 높이가 1 이라면 경우의 수가 1가지 밖에 없으므로 1을 리턴해준다 (line 2)

우선 0으로 이루어진 dp 리스트를 하나 만들어 주는데, 그 길이는 n+1로 한다 (line 5)

리스트의 각 인덱스에 경우의 수를 저장하기 위해서이다.

이때 계단 높이 1까지 도달하기 위한 경우의 수는 1가지 (line 6)

계단 높이가 2까지 도달하기 위한 경우의 수는 2가지 (1칸 이동 + 1칸 이동 or 2칸 이동) (line 7)

를 dp 리스트에 업데이트 해준다.

그리고 n=3 부터 n+1 까지 for loop를 돌려주는데 (line 9)

계단 높이가 n이기 때문에 n+1까지 loop를 돌린다 ((n+1) 포함 안됨)

그리고 문제 접근법에 설명한대로 계단 n 칸에 도달하기 위한 경우의 수는

n-1칸 까지 도달하기 위한 경우의 수와 n-2칸 까지 도달하기 위한 경우의 수의 합이다 (line 10)

최종적으로 dp [n]을 출력해주면 된다.

 

 

문제 풀이 코드

def climbStairs(n):
    if n == 1:
        return 1
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]
 
# Test cases
print(climbStairs(4))  # Output: 5
print(climbStairs(3))  # Output: 3
 

 

 

이 문제는 dynamic programming의 대표적인 문제다.

추가로 문제 조건이 1칸, 2칸, 혹은 3칸씩 올라갈 수 있다고 바뀌더라도

dp [1], dp [2], dp [3]에 대한 값만 바뀔 뿐

문제에 대한 접근방식은 동일하다.

이상 리트코드 문제풀이 70번 climbing stairs 였다.

 

 

관련 문제

리트코드 55번 Jump game 문제 풀이 링크

리트코드 62번 Unique paths 문제 풀이 링크

리트코드 91번 Decode ways 문제 풀이 링크

리트코드 139번 Work break problem 문제 풀이 링크

리트코드 198번 House robber 문제 풀이 링크

리트코드 213번 House robber II 문제 풀이 링크

리트코드 300번 Longest increasing subsequence 문제 풀이 링크

리트코드 322번 Coin change 문제 풀이 링크

리트코드 1143번 Largest Common Subsequence 문제 풀이 링크

 

70. Climbing stairs