[Python | 파이썬] 백준 10844 쉬운 계단 수

[Python | 파이썬] 백준 10844 쉬운 계단 수

 

 

마지막 글자가 0부터 9까지 존재할 수 있으므로 이를 각 열로 하고 각 행은 0~n까지로 하는 배열 dp를 선언한다.

한 자릿수는 모두 1로 초기화한다. (i == 1)

두자리 이상의 수는 만약 맨 뒤에 글자가 0이라면 뒤에서 두번째 글자는 반드시 1이 와야 한다. 따라서 길이가 i-1이고 마지막 글자가 1인 dp[i-1][1]의 값으로 갱신한다.

dp[i][0] = dp[i-1][1]

맨 뒤의 글자가 9인 경우에도 뒤에서 두번째 글자는 반드시 8이 와야 한다. 따라서 길이가 i-1이고 마지막 글자가 8인 dp[i-1][8]의 값으로 갱신한다.

dp[i][9] = dp[i-1][8]

0과 9 이외에는 마지막에서 두번째에 올 수 있는 수는 마지막 수보다 1 작은 수, 1 큰 수 총 2개가 존재하므로 각각의 경우의 합으로 갱신한다.

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

n = int(input())
cnt = 0
dp = [[0] * 10 for i 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 == 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])%1000000000)

https://www.acmicpc.net/problem/10844