문제

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

풀이

처음 문제를 접했을 때 금방 풀 수 있을 것 같아 '이게 왜 실버 1이지?' 했읍니다.
금방 큰 코 다쳤지만요..

우선 경우의 수를 전부 써봤습니다.

n = 1
1 2 3 4 5 6 7 8 9
9개

n = 2
10, 12
21, 23
32, 34
43, 45
54, 56
65, 67
76, 78
87, 89
98
17개

n = 3
101, 121, 123
210, 212, 232, 234
321, 323, 343, 345
432, 434, 454, 456
543, 545, 565, 567
654, 656, 676, 678
765, 767, 787, 789
876, 878, 898
987, 989
32개

개수에만 집중해서 보니 일정 패턴이 있더군요.
그래서 여기에 집중해 코드를 작성해봤습니다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1)
dp[1] = 9
if n >= 2:
    for i in range(2, n+1):
        dp[i] = dp[i-1] * 2 - (i-1)
print(dp[n]%1000000000)

1차원 배열을 이용해 수가 증가함에 따라 배열에 값을 저장하는 방식을 사용했는데, 오답이 나왔습니다.
아무리 봐도 이렇게 접근하는 것이 아닌 거 같아 점화식을 다시 작성해봤습니다.

위의 경우의 수를 다시 보니 규칙이 보였습니다.
1과 9(끝자리수)를 제외한 숫자들은 모두 본인 보다 1씩 크고 작은 숫자로 이뤄져 있는 것이 아니겠읍니까..
그래서 자리수(n)과 끝자리수를 이용해서 2차원 배열을 만들어 문제를 풀었읍니다.

dp = [[0] * 10 for _ in range(n+1)]

for i in range(1, 10):
	dp[1][i] = 1

자리수가 1인 숫자는 각 숫자만 담고 있으면 되기 때문에 0을 제외한 위치에 1을 선언했습니다.

계단 수는 각 자리 숫자와 그 다음 자리 숫자 간의 차이가 정확히 1이어야 하는 숫자입니다. 이를 바탕으로 길이가 i이고 마지막 숫자가 j인 계단 수의 개수를 나타내는 dp[i][j]를 다음과 같이 정의할 수 있습니다.

• 마지막 숫자가 0인 경우:
  0의 앞에는 1만 올 수 있습니다.
  dp[i][j] = dp[i-1][j+1]

• 마지막 숫자가 1~8인 경우:
  마지막 숫자가 1~8인 계단수는 앞 숫자가 j+1이거나 j-1이어야 합니다.
  ex) 32, 34
  dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

• 마지막 숫자가 9인 경우:
  9의 앞에는 8만 올 수 있습니다.
  dp[i][j] = dp[i-1][j-1]

이를 이용하여 다음과 같은 코드가 작성 됐습니다.

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j+1] % mod
        elif j == 9:
            dp[i][j] = dp[i-1][j-1] % mod
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] % mod

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0] * 10 for _ in range(n+1)]
mod = 1000000000

# 1 2 3 4 5 6 7 8 9
# 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 90

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

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