백준 10844 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

전형적인 Dynamic Programing 문제다.

전의 값을 바탕으로 앞의 값을 채워나가는 방식으로, 문제에 대한 이해는 다음과 같다.

​

i) 1의 자리 자연수 중 각 자리수 별 가능한 경우의 수

0으로 시작하는 계단 수는 없으므로 dp[1] = [0,1,1,1,1,1,1,1,1,1] 가된다.

​

ii) 2의 자리 자연수 중 각 자리수 별 가능한 경우의 수

1으로 시작하는 두 자리 자연수 중 계단 수는 10, 12 가 있다. 그렇다면 dp[2][0] = 1, dp[2][1] = 1

2로 시작하는 두 자리 자연수 중 계단 수는 21, 23 마찬가지로 dp[2][2] = 2
... 9로 시작하는 두 자리 자연수 중 계단 수는 98 하나 밖에 없다. dp[2][9] = 1

이렇게 종합해 봤을 때 우린 이런 표를 얻을 수 있다.

n = int(input())
dp = [[0 for _ in range(10)] for __ in range(101)]
dp[1] = [0, 1,1,1,1,1,1,1,1,1]

for i in range(2,101):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1] % 1000000000
        elif j == 9:
            dp[i][j] = dp[i-1][8] % 1000000000
        else:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
    
print(sum(dp[n]) % 1000000000 )