[leetcode 2024/02/27] 70. Climbing Stairs

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

Climbing Stairs - LeetCode

 

1. 접근 방법

이 문제를 보자마자 뭔가 규칙의 냄새가 났다.

따라서 각 계단의 개수별로, 생기는 경우의 수들을 적기 시작했다.

 

규칙이 조금씩 보이기 시작하는 4 계단 부터 시작해보자.

 

[계단 4]

- 1111

- 211

- 121

- 112

- 22

 

[계단 5]

- 11111

- 2111

- 1211

- 1121

- 1112

- 221

- 212

- 221

 

이런식으로 생기게 된다. 이를 작성하면서 Combination이 들어간다는 것을 알 수 있었다.

 

두칸 한칸 한칸 이동하게 되는 경우, 두칸이 어디로 들어가야할 지, 3C1 을 통해서 정할 수 있다. 

 

3C1을 통해

두칸 한칸 한칸

한칸 두칸 한칸

한칸 한칸 두칸

이런식으로 경우의 수를 구할 수 있다. 이제 각 경우의 수를 Combination으로 나타내보자.

aCb라고 했을 때, b가 두칸을 이동하는 개수이다.

 

n = 3: 3C0 + 2C1 

n = 4: 4C0 + 3C1 + 2C2

n = 5: 5C0 + 4C1 + 3C2

n = 6: 6C0 + 5C1 + 4C2 + 3C3

n = 7: 7C0 + 6C1 + 5C2 + 4C3

 

가 된다.

여기서 또 규칙을 찾을 수 있다.

aCb 로 시작한다고 했을 때, a = n값으로 시작하며, b = 0으로 시작한다.

이후 다음 단계는 a -= 1, b += 1로 바뀌면서 또 combination을 진행한다. 이때, combination을 멈추게 되는 조건은 a < b 일 때 이다.

a 보다 b가 커지게 된다면 combination을 멈추게 된다. 

 

이를 바탕으로 코드를 작성하였다. 

+ 피보나치와 같다

 

2. 코드

class Solution:
    def climbStairs(self, n: int) -> int:
        def factorial(n):
            return_value = 1
            for i in range(1, n + 1, 1):
                return_value *= i

            return return_value

        def combination(n, r):
            mid_v = factorial(n) / factorial(n - r)
            return mid_v / factorial(r)

        a = n
        b = 0
        total = 0
        while a >= b:
            total += combination(a, b)
            a -= 1
            b += 1

        return int(total)