[leetcode] Climbing Stairs - Python

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제파악

 

이 문제는 계단을 올라가는데 각 칸수에 맞게 올라가는 경우의 수를 세는 것입니다.(1step or 2step)

ex)

1칸은 1개의 방법

2칸은 1+1 , 2 두가지 방법

3칸은 1+1+1, 1+2, 2+1

...

이것의 규칙을 보면 

n칸은 (n-1칸 +1) + (n-2칸 + 1)의 방법입니다.

따라서 초기 경우의 수 1,2를 해시로 입력해주고 해당 n칸까지의 반복문으로 구하였습니다.

 

class Solution:
    def climbStairs(self, n: int) -> int:
        step = {}
        # 4이면은 2에서 2칸으로 4까지가는경우 3에서 1칸으로 4까지가는 경우 합치면된다
        # 4 -> (d[3]+1) + (d[2] +1)
        # 1은1 2는 2
        step[1] = 1
        step[2] = 2
        for i in range(1, n+1):
            if i not in step:
                step[i] = step[i-1] + step[i-2]
            
        print(step)
        return step[n]