[백준(BOJ)] #10844- 쉬운 계단 수 (파이썬, PyPy3)

문제

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

---

문제 풀이

동적 계획법을 사용해 입력받은 자리 수의 계단수에 대한 경우의 수를 구할 수 있습니다.

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

2차원 dp테이블을 다음과 같이 정의합니다.

dp[N 자리 수][N 자리 수에서 맨 뒷자리에 오는 수]

1) 1의 자리 수에서 맨 뒷자리에 올 수 있는 숫자들을 초기화합니다. 이때 0이 맨 앞에 있는 경우에는 계단 수가 될 수 없으므로 0이 됩니다.

 

2) 자리 수가 2일 때 각 숫자에서 맨 뒷자리에 올 수 있는 숫자의 경우의 수를 저장합니다.

 

크기가 2면서 맨 뒷자리 숫자가 0인 경우는 크기가 1이면서 맨 뒷자리 숫자가 1인 경우만 해당됩니다. 즉, 크기가 1이면서 맨 뒷자리 숫자가 1인 계단 수에서 크기가 증가될 때 얻을 수 있는 계단 수의 경우의 수입니다.

 

크기가 2면서 맨 뒷자리 숫자가 1부터 8인 경우는 크기가 1이면서 맨 뒷자리 숫자가 해당 숫자에서 1을 더하고 뺀 경우가 해당됩니다. 즉, 크기가 1이면서 맨 뒷자리 숫자가 해당 숫자에서 1을 더하고 뺀 계단 수에서 크기가 증가될 때 얻을 수 있는 계단 수의 경우의 수입니다.

 

크기가 2면서 맨 뒷자리 숫자가 9인 경우는 크기가 1이면서 맨 뒷자리 숫자가 8인 경우만 해당됩니다. 즉, 크기가 1이면서 맨 뒷자리 숫자가 8인 계단 수에서 크기가 증가될 때 얻을 수 있는 계단 수의 경우의 수입니다.

 

이런 과정을 통해 다음과 같은 점화식을 얻을 수 있습니다.

i = 자리 수, j = 맨 뒷자리에 오는 수

j = 0 일 때, dp[i][j] = dp[i-1][1]
1 <= j <= 8 일 때, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
j = 9 일 때, dp[i][j] = dp[i-1][8]

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    dp = [[0] * 10 for _ in range(N+1)]
    # 1 ~ 9까지. 0은 맨 앞에 올 수 없음
    for i in range(1, 10):
        dp[1][i] = 1

    # dp[자리 수][해당 자리 수에서 맨 뒷자리 숫자]
    # 자리수 i
    for i in range(2, N+1):
        # 숫자 범위 j
        for j in range(10):
            # i에서 맨 뒷자리 숫자가 0이면 
            # i-1에서맨 뒷자리 숫자가 1인 경우만 계단 수로 이어갈 수 있음
            if j == 0:
                dp[i][j] = dp[i-1][1]
            # i에서 맨 뒷자리 숫자가 9이면 
            # i-1에서맨 뒷자리 숫자가 8인 경우만 계단 수로 이어갈 수 있음
            elif j == 9:
                dp[i][j] = dp[i-1][8]
            # 그 외에는 맨 뒷자리 숫자 +-1
            else:
                dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]
    print(sum(dp[N]) % 1000000000)

결과