10844 - 쉬운 계단 수
📌 문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
📋 코드
N = int(input())
dp = [[0] * 10 for i in range(N+1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
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]) % (10 ** 9))💡 한마디
2차원 dp 테이블을 만들어서 풀었다.
- dp[자리수][마지막 숫자]
예를 들어 dp[2][3] 인 경우 2자리면서 3으로 끝나는 경우의 수이다. 계단 수에서 각 자리수마다 1씩 차이나기 때문에 0은 1로부터 만들어질 수 있고, 9는 8로부터 만들어질 수 있다. 5와 같은 그 외 숫자들은 4 (5-1), 6(5+1) 두 경우에서 올 수있다.
