baekjoon - 10844

problem. 계단 수 = 인접한 수가 1씩 차이가 나는 수임. (a-b) = ±1이라는 말, 길이가 n인 계단 수의 갯수를 구하는 문제

※ 0으로 시작 x 그러나 10은 가능

 

key point 

1	2
1, 2, 3, 4, 5, 6, 7, 8, 9 = 9개 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]	10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 = 17개 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]

1 -> 2로 갈 때 특별한 규칙은 맨 마지막 숫자의 경우 0, 9 -> 1, 8의 갯수에 영향을 받고, 나머지 1, 2, 3, 4, 5, 6, 7, 8은 이전 배열의 ±1한 값들의 덧셈이라는 것이다.

0 = dp[1][1], 1 = dp[1][0] + dp[1][2], ..., 9 = dp[1][8]

그래서 규칙을 알고리즘으로 작성하면

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