[DP] 백준 10844번 “쉬운 계단 수” Python 풀이

문제 링크

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

풀이

• 자릿수 N이 주어졌을 때, 해당 자릿수의 자연수 중에서 계단 수를 만족하는 자연수는 몇개인지?

  • 1의 자리 자연수들 중, 1~9는 계단 수를 만족하므로, 총 9개가 계단 수가 됩니다.

• 해당 문제는 아래 점화식과 2차원 DP 테이블을 사용해 해결할 수 있습니다.

  • dp[자릿수][해당 자릿수에서 가장 뒤에 오는 숫자] = 경우의 수

• 해당 점화식은 아래와 같이 세분화할 수 있습니다.

  • 가장 뒤에 오는 숫자 = 0
    • dp[자릿수][0] = dp[자릿수 - 1][1]
      • 0의 앞에는 1만 올 수 있기 때문입니다.
  • 가장 뒤에 오는 숫자 = 1~8
    • dp[자릿수][가장 뒤에 오는 숫자] = dp[자릿수 - 1][가장 뒤에 오는 숫자 - 1] + dp[자릿수 - 1][가장 뒤에 오는 숫자 + 1]
      • 1~8의 앞에는 +-1이 올 수 있기 때문입니다.
  • 가장 뒤에 오는 숫자 = 9
    • dp[자릿수][9] = dp[자릿수 - 1][8]
      • 9의 앞에는 8만 올 수 있기 때문입니다.

• 따라서, N이 3일 때의 2차원 DP 테이블은 아래와 같이 완성됩니다.

              각 자릿수에서 가장 뒤에 오는 숫자(0~9)
              0  1  2  3  4  5  6  7  8  9
    자릿수(0)   0  0  0  0  0  0  0  0  0  0
    자릿수(1)   0  1  1  1  1  1  1  1  1  1
    자릿수(2)   1  1  2  2  2  2  2  2  2  1
    자릿수(3)   1  3  3  4  4  4  4  4  3  2

• 결과적으로, N번째 자릿수의 경우의 수를 모두 합한 뒤, 1,000,000,000으로 나눈 나머지를 출력하면 정답이 됩니다.

코드

import sys

n = int(sys.stdin.readline())

# DP 테이블 초기화
dp = [[0] * 10 for _ in range(n+1)]

# 1의 자릿수의 경우의 수 초기화
for i in range(1, 10):
    dp[1][i] = 1

# 나머지 자릿수의 경우의 수 탐색
for i in range(2, n+1):
    for j in range(10):
        # 가장 뒤에 오는 숫자가 0일 땐, 그 앞에 1만 올 수 있습니다.
        if (j == 0):
            dp[i][j] = dp[i-1][1]

        # 가장 뒤에 오는 숫자가 1~8일 땐, 그 앞에 +-1이 올 수 있습니다.
        elif (1 <= j <= 8):
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

        # 가장 뒤에 오는 숫자가 9일 땐, 그 앞에 8만 올 수 있습니다.
        else:
            dp[i][j] = dp[i-1][8]

#  N번째 자릿수의 경우의 수를 모두 합한 뒤, 
# 1,000,000,000으로 나눈 나머지를 출력하면 정답
print(sum(dp[n]) % 1000000000)

참고

• https://pacific-ocean.tistory.com/151