문제
문제 : https://www.acmicpc.net/problem/10844
45656과 같이 인접한 자리수의 차이가 1인 수를 계단 수라고 한다.
수의 길이 n이 주어질 때, 길이가 n인 계단 수의 계수를 구하여라. 단, 0부터 시작하는 수는 계단 수가 아닌 것으로 취급한다.
접근
이 문제는 2024.04.04 - [백준] 11057 - 오르막 수와 비슷하게 동적 계획법으로 접근할 만한 문제다.
수의 길이가 1일 때, 계단 수의 1부터 9까지 수가 해당된다.
그리고 수의 길이가 2인 경우, 각 자리 수 마다 계단 수는 다음과 같이 생성할 수 있다.
개수를 표시하면 아래 그림과 같다.
참고로 0으로 시작하는 수의 개수는 다음 길이의 계단 수의 개수를 구할 때 구하기 위해서 구해야 한다. 즉, 숫자 01은 101을 만들기 위해서 필요하다.
동일하게 길이가 3인 계단 수의 계수는 아래 그림과 같이 구할 수 있다.
규칙을 보면 길이가 n이고 자리수가 0인 계단 수의 개수는 n - 1 길이의 계단 수 중에서 자리 수가 1인 계단 수의 개수와 동일하다.
길이가 n이고 자리수가 9인 계단 수의 개수는 n - 1 길이의 계단 수 중에서 자리 수가 8인 계단 수의 개수와 동일하다.
나머지는 n이고 자리수가 1 이상 8 이하인 계단 수의 개수는 n - 1 길이의 계단 수 중에서 자리 수가 인접한 계단 수 개수의 합과 동일하다. 이를 점화식으로 표현하면 다음과 같다.
$$ dp[n][i] = \begin{cases} 1, & \mbox{if } n = 1\\ dp[n-1][i + 1], & \mbox{if } n > 1 \& i = 0 \\ dp[n-1][i + 1] + dp[n-1][i + 1] , & \mbox{if } n > 1 \& 1 \le i \le 8 \\ dp[n-1][i - 1], & \mbox{if } n > 1 \& i = 9 \end{cases}$$
구한 점화식을 구현하여 문제를 해결해보자.
풀이
1. 계단 수의 길이 입력
n = int(sys.stdin.readline().strip())
2. 출력 시 나머지 연산할 값 초기화
divided = 1000000000
3. 메모이제이션 테이블 초기화
dp = [[1 for i in range(10)] for j in range(n)]
3. 점화식 구현
저장한 값이 너무 커지지 않도록 나머지 연산하여 저장한다.
for i in range(1, n):
for j in range(0, 10):
if j == 0:
tmp = dp[i - 1][j + 1]
elif j == 9:
tmp = dp[i - 1][j - 1]
else:
tmp = dp[i - 1][j - 1] + dp[i - 1][j + 1]
dp[i][j] = tmp % divided
4. 출력
테이블의 마지막 원소 중 인덱스 1부터 9까지의 값을 더한 뒤 나머지 연산한 값이 출력할 결과가 된다.
print(sum(dp[-1][1:]) % divided)
참고 문서
https://www.acmicpc.net/problem/10844