문제
- 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
- N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
- 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
아이디어
- n = 1. 9개
- 1, 2, 3, 4, 5, 6, 7, 8, 9
- n = 2. 17개
- 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98
- n = 3.
- 101, 121, 123, 212, 232, 234, 323, 343, 434, 454, , 989
- n = 4.
- 1010
규칙
끝나는 자리수
0 1 2 3 4 5 6 7 8 9
0 0 1 1 1 1 1 1 1 1 1
1 1 1 2 2 2 2 2 2 2 1
2 ....
- V자로 더해지고 있다.
- 즉, 정리해 보면 다음과 같다.
L = 0 => dp[N][L] = dp[N - 1][L + 1]
L = (1 ~ 8) => dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
L = 9 => dp[N][L] = dp[N - 1][L - 1]
코드
python
N = int(input())
dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
dp[1][i] = 1
MOD = 1000000000
for i in range(2, N+1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i-1][1]
elif j == 9:
dp[i][j] = dp[i-1][8]
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[N]) % MOD)