학구적인 코브라의 IT 리뷰

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

정상까지 n개의 계단이 있는데 한 번에 한 칸 아니면 두 칸만 올라갈 수 있다. 얼마나 많은 unique 한 방법으로 정상까지 도달할 수 있느냐? 하는 문제이다. 저번 Unique Paths 문제와 비슷하게 출발점에서 도착점까지 가는 모든 방법의 수를 찾는 문제이므로 이 문제도 bfs로 접근할 수 있겠지만, 저번 문제를 풀 때와 같이 점화식을 찾으면 좀 더 쉽게 문제를 해결할 수 있다.

n번째 계단에 도달하기 위해서는 무조건 n-1번째 계단 아니면 n-2번째 계단을 밟아야만 한다. 이 두 계단을 통해서만이 n번째 계단에 도달할 수 있는 것이다. 이를 통해 아래와 같은 점화식을 유추해낼 수 있다.

n번째 계단에 가는 방법 = n-1번째 계단에 가는 방법 + n-2번째 계단에 가는 방법
path[n] = path[n-1] + path[n-2]

코드로 풀어서 써보자면 아래와 같다.

class Solution:
    def climbStairs(self, n: int) -> int:
        path = [1 for _ in range(n + 1)]
        
        for i in range(2, n+1):
            path[i] = path[i-1] + path[i-2]
                
        return path[n]

path라는 리스트는 n+1 길이로 만들어주고 초기값을 1로 채워준다.

2번째 계단부터 새로 값을 계산해서 넣어줄 예정이라 초기값이 무엇인지 중요하지 않을 수도 있지만, 첫 번째 계단은 반드시 출발점에서 한 칸만 밟고 오는 한 가지 경우밖에 없고 또 path[2]부터 점화식을 사용하기 위해서라면 0번째 계단(출발점)에도 값 1을 넣어주는 것이 더 편하기 때문이다.

2번째 계단에 오르는 경우의 수는 문제 1번 예제와 같이 1칸+1칸 혹은 2칸 이렇게 두 가지 경우의 수밖에 없다.

즉, 2번째 계단에 가는 방법은 한 칸 전에서 올라오거나, 출발점에서 2칸을 바로 올라오거나 이 두가지 경우의 수밖에 없는 것이다.

이렇게 path[0] == path[1] == 1 값을 채워주고 path[2]부터는 점화식 알고리즘을 적용해 문제를 풀면 된다.

주어진 계단 크기인 n번을 한 번만 훑기 때문에 시간 복잡도도 O(n)이 나오게 된다.

Easy 문제는 이렇게 간단하게 해결. ^-^