[LeetCode] 70. Climbing Stairs

 n이라는 input이 주어졌고 이는 계단의 높이로 계단은 한 번에 한 개 혹은 두 개를 오를 수 있고, 가장 높은 계단에 오를 수 있는 경우의 수를 구하는 것이다. 아래 제공된 솔루션은 한 개와 두 개를 오를 때 필요한 개수를 조합해 각 개수에 따른 경우의 수(number of cases)를 구해 하나씩 더해 나가는 것이다.

 

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

 

class Solution:
    def climbStairs(self, n: int) -> int:
        ret = 1
        one = two = 0
        
        if (n % 2) == 1:
            n -= 1
            one += 1
        
        while n > 0:
            n -= 2
            two += 1

        while two > 0:
            cnt = one + two

            numerator = 1
            for i in range(cnt):
                numerator *= (i+1)

            denominator1 = denominator2 = 1
            for i in range(one):
                denominator1 *= (i+1)
            for i in range(two):
                denominator2 *= (i+1)

            ret += numerator // (denominator1 * denominator2)

            two -= 1
            one += 2

        return ret

 

참고

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