- Dynamic Programming
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이과정
DP 문제가 늘 그렇듯이 규칙을 찾아내면 쉽다.
이 문제의 핵심은 인접한 모든 자리의 차이가 1인 수이다.
N=2일 때를 생각해보자.
맨 앞자리가 0일 때는 0으로 시작하므로 계단수가 아니다.
0일 때는 두번째 자리로 1이 올 수 있다. (-1은 음수이므로 제외)
1일 때는, 두번째 자리로 0 또는 2가 올 수 있다.
9일 때는, 두번째 자리에 8이 올 수 있다. (10은 한자리 수 가 아니므로 제외)
즉, 맨 앞자리의 값이 i라고 할 때, 그 뒤에 따라올 수 있는 숫자는 i-1, i+1이다.
N=n일 때 계단수는 어떤 숫자 i 뒤에, 맨 앞 값이 i+1, 또는 i-1인 n-1 길이의 계단수를 추가한 것이므로 이를 활용하여 개수를 구할 수 있다.
코드
import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
dp = [[0] * 10 for _ in range(N+1)]
for i in range(1, 10):
dp[1][i] = 1
for i in range(2, N+1):
for j in range(10):
if j - 1 >= 0:
dp[i][j] += dp[i-1][j-1]
if j + 1 < 10:
dp[i][j] += dp[i-1][j+1]
result = 0
for x in dp[N]:
result += x
result %= 1000000000
print(result)
