박종훈 기술블로그

(Leetcode) 70 - Climbing Stairs

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

이 문제는 DP 문제이다.

처음에는 아래와 같이 작성하였다.

class Solution:
    def climbStairs(self, n: int) -> int:
        return self.select(1, n) + self.select(2, n)

    def select(self, step, left) -> int:
        if left < step:
            return 0
        if left == step:
            return 1

        left = left - step

        return self.select(1, left) + self.select(2, left)

문제는 풀리긴 한다.
그런데 n 값이 커질수록 시간이 엄청나게 늘어나게 된다. 그래서 수정이 필요하였다.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.calc(n)

    def calc(self, n: int) -> int:
        dict = {}

        dict[1] = 1
        dict[2] = 2

        for i in range(3, n + 1):
            dict[i] = dict[i-1] + dict[i-2]

        return dict[n]

그래서 규칙을 찾아 위와 같이 수정하여 통과하였다.

규칙성만 찾으면 풀 수 있는 문제이기 때문에 따로 정리는 하지 않는다.

펜으로 경우의 수를 찾아가면서 풀었는데 뭔가 수능 수학을 다시 푸는 기분이 들었다.

scratch