[BOJ] 10844 쉬운 계단 수 - python

 

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

 

계단 수는 23, 454처럼 각 자리수가 1씩 차이나는 수를 말한다.

10844 쉬운 계단 수는 N이라는 입력을 받았을 때, N 자리 계단수의 총 개수를 출력하는 문제였다.

 

DP 문제였는데, 점화식을 세우는 부분이 조금 어려웠다.

 

 

N==1, 한 자리 수라면,

1,2,3,4,5,6,7,8,9 총 9개의 계단 수를 갖는다.

 

N==2, 두 자리 수라면,

10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98

총 17개의 계단 수를 갖는다.

 

 

4자리 수의 마지막이 7로 끝나는 계단 수의 경우의 수를 찾아보자.

_ _ _ 7

 

7 앞에는 6 또는 8이 와야한다.

_ _ 6 7 or _ _ 8 7

 

이제 7은 떼내고, 세 자리수 _ _ 6과 _ _ 8의 경우의 수를 찾으면 된다.

 

6과 8 앞에도 각각 5,7과 7,9가 와야한다. 

_ 5 6 / _ 7 6 / _ 7 8/ _ 9 8

 

또 다시 두 자리 수 _ 5 / _ 7 / _ 8 / _ 9의 경우의 수를 찾으면 된다.

4 5 / 6 5 / 6 7 / 8 7 / 7 8 / 9 8 / 8 9

 

첫 째 자리까지 찾은 결과, 7로 끝나는 4자리 계단 수는 총 7개라는 것을 알 수 있다.

 

-> 같은 풀이 과정이 반복되는 것을 확인할 수 있다. 

 

이를 표를 통해 살펴보겠다.

각 N 자리 수 수에서 가장 마지막 자리에 올 수 있는 숫자의 경우의 수 표이다. 

 

 

위 풀이를 토대로 살펴보면, 각 자리수는 자신의 자리수-1의 양 옆 수의 합이라는 사실을 알 수 있다.

 

4 자리 수의 7의 경우의 수를 살펴보면

3 자리수 6과 8을 더한 수 이고,

 

3 자리수의 6과 8은

2 자리수 5와 7을 더한 수는 3의 자리 6의 경우의 수이고,

7과 9를 더한 수는 3 자리수 8의 경우의 수라는 것을 알 수 있다.

 

즉, 표를 기준으로 자신의 대각선 수를 더한 값이 자신의 경우의 수가 된다. 

 

이를 바탕으로 점화식을 세울 수 있다.

K = 0,      dp[N][0] = dp[N-1][1]

K = 9,      dp[N][9] = dp[N-1][8]

K = 1~8,   dp[N][K] = dp[N-1][K-1] + dp[N-1][K+1] 

 

 

import sys

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

dp = [[0 for i in range(10)] for j in range(101)]

for k in range(1, 10):
    dp[1][k] = 1

for n in range(2, N + 1):
    for k in range(10):
        if k == 0:
            dp[n][k] = dp[n-1][1]
        elif k == 9:
            dp[n][k] = dp[n-1][8]
        else:
            dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1]

print(sum(dp[n]) % 1000000000)