[Python] ClimbingStairs

Easy 난이도 문제로 Acceptence 48.8%의 문제

 

계단을 1칸 or 2칸씩 오르는 방법을 구하는 문제로

가능한 모든 경우의 수를 구하는 문제다.

 

수학의 경우의 수를 구하는 기호인 nCr을 함수로 만들어 모든 경우의 수를 구한다.

 

class Solution(object):
    def __init__(self):
        self.caseSum = 0

    def nCr(self, n, r):
        denominator = numerator = 1
        for x in range(n-r+1, n+1):
            numerator *= x
        for x in range(1, r+1):
            denominator *= x        
        return numerator//denominator

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        maxTwo = n // 2
        for numTwo in range(maxTwo + 1):
            self.caseSum += self.nCr(n - numTwo, numTwo)
        return self.caseSum