[NeetCode/Python] Climbing Stairs

문제 링크: https://neetcode.io/problems/climbing-stairs

NeetCode

 

단순한 조합 문제라고 생각했다. 이런 비슷한 문제를 예전에 풀었지만 나중에야 기억이 났는데.. 암튼 초반에 그래서 삽질을 좀 했다.

 

[초반 틀린 풀이]

from itertools import permutations

class Solution:
    def climbStairs(self, n: int) -> int:
        # 조합 구하기 + 순서 고려
        
        result = 1 # consist of all 1s + possible 2s
        for i in range(1, n//2 + 1): # i = num of 2
            goal = n
            numOf1s = goal - i * 2
            numbers = [2 for b in range(i)]
            numbers.extend([1 for a in range(numOf1s)])
            result += permutations(numbers, len(numbers))

        return result

 

먼저 식에 들어갈 수 있는 2의 최대 개수부터 시작해서 줄여나갔다. 그러면 2와 1의 조합은 쉽게 구할 수 있는데, 문제는 이게 조합이 아니라 순열이었다는 점이다!

문제를 꼼꼼히 보지 않아서 몰랐는데, 2+1 과 1+2를 다르게 여겼다.

그래서 itertools의 permutations을 사용하려고 했는데 안타깝게도 NeetCode는 itertools을 사용할 수 없게 해서 다른 방법을 써야했다.

 

[최종 코드]

from itertools import permutations

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3:
            return n
        
        n1, n2 = 2, 3
        
        for i in range(4, n+1):
            temp = n1 + n2
            n1 = n2
            n2 = temp

        return n2

 

생각해보니까 이전(n-1)의 결과에 1을 더한 수, 그리고 그 전(n-2) 수에 2를 더한 수가 바로 현재 n 이었다.

고로 n을 만드는 방법은 n-1와 n-2의 방법의 수를 구하기만 하면 된다는 사실을 발견했다!!

피보나치와 같다고 생각하면 된다!

(이런 패턴을 찾아내는 힘을 다시 길러야 겠다.. 허허 바로 생각해냈어야 했는데 코테 안푼지 오래됐어 뇌가 굳은듯)

 

시간 복잡도

n <= 3 일 경우 O(1)

n >3 일 경우 O(n)