LeetCode 70(Climbing Stairs, Python)

1. 문제 링크

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

2. 문제 설명

• 계단을 n steps에 거쳐 올라가며, 한번에 1 or 2 steps 씩밖에 오르지 못할 때, n개 계단을 오르는 방법의 수를 반환
  
  • 예시1) n=2 이면 1step + 1step / 2steps 이렇게 두가지 방법이 가능하므로 2를 반환
  • 예시2) n=3 이면 1step + 1step + 1step / 1step + 2steps / 2steps + 1steps 세 방법이 가능하므로 3을 반환 → 규칙을 찾아야하는 문제

3. 처음 풀이 

• 2~7 steps 까지를 나열해보며 규칙을 찾았다. (물론 더 쉬운 규칙이 있었음) 
  • 3 step = 1 step으로 3번 움직이거나, 2step과 1step으로 움직이는 방법. 2step 1step은 순서 고려해야 함
    • 일반화하면 1 + 2C1 
  • 4 step = 1 step 3번, 3step 1step, 2step 2step 
    • 일반화하면 1 + 3C1 + 2C2 
  • 5step = 1 + 4C3 + 3C2 
• 순열 경우의수를 구하는 함수를 만들어두고, for문을 돌리며 합을 계산

class Solution:
    def climbStairs(self, n: int) -> int:
        
        def comb_count(a,b): # 콤비네이션 경우의수 계산식
            top = 1
            down = 1
            for i in range(b):
                top = top * (a-i) 
            for i in range(b):
                down = down * (b-i)
            return int(top/down)
        
        case_count = 1 # 1을 default로 셋팅하고

        for i in range((n-1)//2): 
            case_count += comb_count(n-1-i, 1+i) # (n-1)C1 + (n-2)C2 +.. 를 합산
        
        if n % 2 == 0: # n이 짝수면 1을 끝에 더해줌 
            case_count += 1 
        
        return case_count

 

4. 다른 풀이 

• 피보나치수열인데 바로 간파하지 못했다. 
• 결국 이전 값과 현재값을 더하면 되는 구조
  • 1step의 경우의 수가1, 2step의 경우의 수가 2 → 3step 은 1+2 → 4stepdms 1+2+3으로 계산이 됨

class Solution:
    def climbStairs(self, n: int) -> int:
        stair=[1,2] # 우선 1step, 2step에 대한 경우의 수를 채운 뒤
        while len(stair)<n:
            stair.append(stair[-1]+stair[-2]) # 가장 마지막 결과와 그 이전 결과를 더한 걸 append
        return stair[n-1]

5. 배운 점 

• 규칙 잘찾기.. 피보나치인데 다른규칙으로 찾느라 헤맸음
  • 수학에선 피보나치수열이지만, 동적계획법(Dynamic Programming)의 대표적인 예시가 피보나치