[LeetCode] 70번 Climbing Stairs 문제 풀이 (파이썬)

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

Climbing Stairs - LeetCode

이거 DP일것 같다고 직접 그래프도 그려놓고선 왠지 자신이 없어서 다른 방법 고민하다가 시간 너무 많이 썼다. 뭔 itertools permutations 이런거 찾아보고 divmod로 고민해보고 증말........ 진짜 속쓰리다. 결론부터 말하면 너무나도 DP인 문제 맞다.

 

n = 5라고 했을 때

(5 - 1)인 4, (5 - 2)인 3 두 가지 경우 각각에의 가짓수만 구해서 더해주면 답이 나온다.

다시 말해, 5로 가기 위해서는

4로 가는 모든 경우의 수 (+ 1개의 계단)

그리고 3으로 가는 모든 경우의 수 (+ 2개의 계단)

이 두가지 경우만 고려해주면 된다는 것.

 

즉 스텝이 1, 2 두 가지 경우밖에 없으니

n번째로 가기 위해서는 이전 단계에서 n - 1번째 계단에 있었거나 n - 2번째 계단에 있었거나 두 가지 경우밖에 없다.

그리고 이는 n - 1, n - 2번째 계단 각각에 대해서도 마찬가지이다.

즉 문제가 최적 부분 구조로 나뉘어지며,

조금만 생각해보면 알겠지만 이 부분 문제들은 중복된다.

따라서 너무나도 전형적인 다이나믹 프로그래밍 문제가 된다.

 

피보나치 수열이나 마찬가지인 문제라고 보면 되고, 그것을 대충 생각해냈지만 뻘짓을 많이 한 나는 오랜 시간의 사투 끝에 16ms의 답을 제출해냈다. 근데 소요시간은 솔직히 같은 답안으로 해도 천차만별로 나와서 그냥 인터넷 속도빨인 것 같다....

 

구현은 간단하게 바텀 업 방식으로 했다.

class Solution:
    def climbStairs(self, n: int) -> int:
        d = [0] * 46
        
        if n == 1:
            return 1
        
        d[1] = 1
        d[2] = 2
        
        for i in range(3, n + 1):
            d[i] = d[i - 1] + d[i - 2]
            
        return d[n]

탑 다운 코드도 간단히 작성해보았다.

class Solution:
    def climbStairs(self, n: int) -> int:
        d = [0] * 46
        
        def climb(x):
            
            if x == 1 or x == 2:
                return x
            
            if d[x] != 0:
                return d[x]
            
            d[x] = climb(x - 1) + climb(x - 2)
            
            return d[x]
            
        return climb(n)