파이썬으로 계단 오르기 방법의 수 구하기 – 동적 프로그래밍 완벽 가이드

계단이 n개 있고, 한 번에 1칸 또는 2칸씩만 오를 수 있다고 가정해 봅시다. 이때 이 계단을 끝까지 오를 수 있는 서로 다른 방법의 개수를 반환하는 함수를 정해야 합니다.

계단을 오르는 순서가 다르면 별개의 방법으로 간주합니다. 즉, 같은 칸수 조합이라도 순서가 다르면 새로운 방법으로 셉니다. 만약 답이 매우 커질 경우에는 결과를 10^9 + 7로 나눈 나머지를 반환하도록 합니다.

문제 예시

예를 들어 입력이 n = 5라면, 출력은 8이 됩니다. 계단을 오르는 방법은 다음과 같이 총 8가지입니다.

• 1, 1, 1, 1, 1
• 2, 1, 1, 1
• 1, 2, 1, 1
• 1, 1, 2, 1
• 1, 1, 1, 2
• 1, 2, 2
• 2, 1, 2
• 2, 2, 1

풀이 접근 방식

이 문제는 대표적인 동적 프로그래밍(Dynamic Programming) 문제로, 피보나치 수열과 동일한 점화식을 사용합니다. i번째 계단에 도달하는 방법의 수는 (i-1)번째 계단에서 1칸 올라오는 경우와 (i-2)번째 계단에서 2칸 올라오는 경우의 합과 같습니다.

구체적인 풀이 단계는 다음과 같습니다.

• 크기가 n+1인 배열 dp를 선언하고 모든 값을 0으로 초기화합니다.
• dp[1] := 1로 설정합니다.
• i가 2부터 n+1까지 반복하면서 dp[i] := dp[i-1] + dp[i-2]를 계산합니다.
• dp 배열의 마지막 원소를 m(10^9 + 7)으로 나눈 나머지를 반환합니다.

파이썬 구현 코드

아래 코드를 통해 더 자세히 이해해 보겠습니다.

m = (10**9) + 7
class Solution:
    def solve(self, n):
        dp = [0 for _ in range(n+2)]
        dp[1] = 1
        for i in range(2, n+2):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1] % m

ob = Solution()
print(ob.solve(5))

입력

5

출력

8

시간 및 공간 복잡도

이 알고리즘은 계단의 개수 n에 대해 한 번씩 순회하므로 시간 복잡도는 O(n), 결과를 저장하는 dp 배열 때문에 공간 복잡도 역시 O(n)입니다. 참고로 두 변수만 사용하면 공간 복잡도를 O(1)까지 줄일 수 있습니다.