10844번: 쉬운 계단 수

10844번: 쉬운 계단 수

DP 문제다.

45656 처럼 인접한 모든 자리의 차이가 1인 수의 개수를 구하는 문제

N이 입력값으로 들어오고, N자리의 계단 수의 개수를 출력하면 된다.

 

먼저, dp[n][i]라는 2차원 리스트 dp 테이블을 만들었다.

해당 dp테이블은 n자리의 계단 수 중 i로 끝나는 계단 수의 개수를 저장하는 dp테이블이다.

 

1자리 계단 수와 2자리 계단수를 직접 써보면서 규칙을 찾을 수 있었다.

만약 n자리 계단 수의 경우, 2가지 경우의 수로 나뉜다.

1. n자리 계단 수이고 끝나는 숫자가 0 또는 9인 경우

이 경우에는 이전 숫자가 1 또는 8인 경우에만 가능하다.

즉, dp[n][0] = dp[n-1][1] / dp[n][9] = dp[n-1][8]

2. n자리 계단 수이고 끝나는 숫자가 1~8인 경우

이 경우에는 이전 숫자가 인접한 2개의 숫자가 가능하다.

즉, dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]

 

 

# 10844번: 쉬운 계단 수
 
n = int(input()) # 자리수
dp = [[0] * 10 for _ in range(101)] # dp 테이블
# dp[n][i] -> n자리의 계단 수 중 i로 끝나는 계단수의 개수

dp[1] = [0, 1, 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][0] = dp[i-1][1]
        elif j == 9:
            dp[i][9] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]


print(sum(dp[n])%1000000000)