[LeetCode]Climbing Stairs

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

Climbing Stairs - LeetCode

 

문제 분석

특정 수의 계단이 있을 때 1칸 혹은 2칸만 오를 수 있다고 가정하면, 계단을 오르는 총 방법은 몇가지가 되는지를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def climbStairs(self, n: int) -> int:
        # F(n) = F(n-1) + F(n-2)
        curr = prev = 1
        for _ in range(n-1):
            curr, prev = curr + prev, curr
        return curr

접근 방법

1. N까지의 계단에 도달하기 위한 경우의 수를 구하기 위해서는 n-1 까지 오른 경우의 수와, n-2 까지 오른 경우의 수를 더합니다.
2. curr, prev를 1로 초기화 하고, 반복문을 순회합니다.
3. curr 값은 n-1을 가리키는 상태이고, prev 값은 n-2를 가리키는 상태입니다.
4. curr와 prev를 더한 값을 curr로 할당하고, prev를 curr로 할당해 계단 올라간 것을 처리합니다.
5. curr을 return 합니다.

 

두번째 시도한 답안

class Solution:
    def climbStairs(self, n: int) -> int:
        # F(n) = F(n-1) + F(n-2)
        dp = [1, 1, 2]

        if n <= 2:
            return dp[n]

        for i in range(3, n+1):
            dp.append(dp[i-1] + dp[i-2])
        
        return dp[n]

접근 방법

1. 피보나치 수열의 초기값을 설정합니다.
2. n이 2보다 작거나 같다면 그대로 return 합니다.
3. 3부터 n까지 반복하여 피보나치 수를 누적합니다.
4. 마지막에 담긴 값을 return 합니다.

첫번째 풀이방법과 동일하지만 동적 프로그래밍을 활용한 방법입니다.

 

예시와 설명

2개의 계단을 오르는 경우의 수

(0, 2) / (1, 1) -> 총 2가지

 

3개의 계단을 오르는 경우의 수

(1, 1, 1) / (1, 0, 2) / (0, 2, 1) -> 총 3가지

 

4개의 계단을 오르는 경우의 수

(1, 1, 1, 1) / (1, 1, 0, 2) / (1, 0, 2, 1) / (0, 2, 1, 1) / (0, 2, 0, 2) -> 총 5가지

 

5개의 계단을 오르는 경우의 수

(1, 1, 1, 1, 1) / (1, 1, 0, 2, 1) / (1, 0, 2, 1, 1) / (0, 2, 1, 1, 1) / (0, 2, 0, 2, 1) / (1, 1, 1, 0, 2) / (1, 1, 0, 1, 2) / (0, 2, 1, 0, 2) -> 총 8가지

 

각 계단을 오르는 경우의 수를 세어보다 보면 피보나치 수열과 같은 규칙을 발견할 수 있다. 즉 n개의 계단을 오르기 위한 경우의 수는 n-1, n-2 에서의 계단을 오르기 위한 경우의 수를 합한 것과 같다.