쉬운 계단 수 10844
- 45656이란 수를 보자
-
이 수는 인접한 모든 자리수의 차이가 1이다. 이런 수를 계단 수라고 한다.
- N을 입력 받아서, 길이가 N인 계단 수가 몇 개 있는지 알아보자.
- 첫째 자리에 올 수 있는 수는 1~9이다.
- 첫째 자리수가 1이라면 둘 째 자리수는 0또는 2가 올 수 있다.
- 만약 첫째 자리수가 9라면 둘 째 자리수는 8만 올 수 있다.
풀이 방법
- N=1일 경우, 0은 계단 수가 아니다.
- N = 1,2일 경우 N은 N-1 일 때 수에서 +-1을 1의 자리에 붙인다는 것을 알 수 있다. 길이가 N일 때, 마지막 수가 L일 경우의 계단 수 dp[N][l] = dp[N-1][l-1] + dp[N-1][l+1]
- 위 점화식은 L이 1~8일 때에만 성립한다
-
0은 +1을 한 1만 허용되고, 9는 -1을 한 8만 적용되기 때문이다.
-
따라서 이를 정리 하면 아래와 같다. 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]
- 이해하기가 정말 어려웠는데, 아래 참고 블로그의 표를 보면서 겨우 겨우 이해할 수 있었다.
n = int(input())
d = [[0]*10 for _ in range(n+1)]
ans, mod = 0, 1000000000
def solve():
for i in range(1, 10):
d[1][i] = 1
for i in range(2, n+1):
for j in range(0, 10):
if j > 0:
d[i][j] += d[i-1][j-1]
if j < 9:
d[i][j] += d[i-1][j+1]
d[i][j] %= mod
solve()
print(sum(d[n]) % mod)