[BOJ] 10844번 : 쉬운 계단 수

🔒 문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

⌨ 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

🖨 출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

📚 예제

Ex1)

1

9

Ex2)

2

17

📌 풀이

dp[계단 수][일의 자리 수] 로 행렬을 만든다.
행렬에는 각 인덱스 별 만들 수 있는 계단 수를 저장한다.

dp[n][m]으로 가정하자.

1. N == 1 일 때

n == 0 일 때, m이 0인 경우를 제외하고는 모두 1이다. m이 0인 경우는 0이다. (0으로 시작 못하니까)

dp[0][0] = 0
dp[0][1] = 1
dp[0][2] = 1
dp[0][3] = 1
dp[0][4] = 1
dp[0][5] = 1
dp[0][6] = 1
dp[0][7] = 1
dp[0][8] = 1
dp[0][9] = 1

2. N이 2 이상일 때

1) m == 0
dp[n][m] = dp[n-1][m+1]

2) m == 9
dp[n][m] = dp[n-1][m-1]

3) 나머지
dp[n][m] = dp[n-1][m-1] + dp[n-1][m+1]

정답은 마지막 행의 모든 인수를 더하면 된다.

🔑 python 코드

import sys
N = int(sys.stdin.readline())
dp = [[0 for _ in range(10)] for _ in range(N)]
ans = 0
for i in range(1,10):
    dp[0][i] = 1

for i in range(1,N):
    for j in range(10):
        if(j == 0):
            dp[i][j] = dp[i-1][j+1] # 끝자리가 0이면 1밖에 못붙임
        elif(j == 9):
            dp[i][j] = dp[i-1][j-1] # 끝자리가 9일때 8이 붙는 경우
        else:
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]

for i in range(10):
    ans+=dp[N-1][i]