[Algorithm][LeetCode][Easy][Python] 70. Climbing Stairs

문제는 여기서 볼 수 있다.

 

 

문제가 정말 심플하면서 Dynamic Programming(이하 DP) 방식의

 

기초 활용법을 느낄 수 있는 문제라 생각하여 포스팅한다.

 

---

 

분석

문제는 아주 간단하다.

 

n개의 계단이 있는 꼭대기까지 도달 가능한 경우의 수를 구하는 문제다.

 

대신 한 번에 1개 혹은 2개의 계단을 올라갈 수 있다.

 

 

처음부터 경우의 수를 따져보면 쉽게 패턴을 발견할 수 있다.

 

(1)은 1개의 계단을 올라가는 기호,

 

(2)는 2개의 계단을 올라가는 기호로 사용하겠다.

 

if n == 1:

경우의 수는 아래 딱 한 가지뿐이다.

 

- (1)

 

if n == 2:

경우의 수는 아래 두 가지이다.

 

- (1) (1)

- (2)

 

if n == 3:

경우의 수는 아래 세 가지이다.

 

- (1) (1) (1)

- (1) (2)

- (2) (1)

 

 

이런 종류의 문제를 많이 풀어본 사람이라면

 

여기서 벌써 패턴을 발견할 수 있겠지만 두 단계만 더 가보자.

 

if n == 4:

경우의 수는 아래 다섯 가지이다.

 

- (1) (1) (1) (1)

- (1) (1) (2)

- (1) (2) (1)

- (2) (1) (1)

- (2) (2)

 

if n == 5:

경우의 수는 아래 여덟 가지이다.

 

- (1) (1) (1) (1) (1)

- (1) (1) (1) (2)

- (1) (1) (2) (1)

- (1) (2) (1) (1)

- (2) (1) (1) (1)

- (1) (2) (2)

- (2) (1) (2)

- (2) (2) (1)

 

 

풀이

n이 3 이상일 때, 경우의 수는 아래와 같다.

 

(n의 경우의 수) = (n-1의 경우의 수) + (n-2의 경우의 수)

 

왜일까?

 

 

n-1일 때, n에 도달하려면 딱 1개의 계단만 더 가면 되고,

 

n-2일 때, n에 도달하려면 1개 혹은 2개의 계단만 더 가면 되기 때문이다.

 

 

좀 더 이해하기 쉽도록 n이 4일 때를 보자.

 

n-1은 3이므로 해당 경우의 수마다 뒤에 (1)을 붙이면

 

n에 도달하는 경우의 수들 중 일부가 된다.

 

 

또한, n-2은 2이므로 해당 경우의 수마다 뒤에 (1) 혹은 (2)를 붙일 수 있는데,

 

(1)를 붙이게 되면 n-1인 경우의 수와 겹치게 되므로

 

(2)만 붙여주면 된다.

 

 

그래서 위와 같은 식을 구할 수 있는 것이다.

 

 

코드는 아래와 같으며 꽤 준수한 퍼포먼스를 보여준다.

 

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [1, 2] + ([0] * (n-2))
        for idx in range(2, n):
            dp[idx] = dp[idx-1] + dp[idx-2]
        return dp[n-1]

 

---

 

끝!