Baekjoon 10844

해당 문제는 여기에서 확인 가능합니다.

해당 문제는 주어진 길이 N에 대해 각 자릿수가 연속된 계단 수의 개수를 구하는 문제입니다.
여기서 연속된 계단 수란 인접한 자릿수의 차이가 1인 수를 의미합니다. 예를 들어, 123, 321, 876 등이 연속된 계단 수입니다. 문제의 조건에 따라 0으로 시작하는 수는 계단 수가 아니므로 고려하지 않아도 됩니다.
숫자의 길이가 N일 때, 마지막 자리 숫자에 따라서 그 앞의 자리 숫자가 어떤 숫자인지에 따라 경우의 수가 달라지므로 다음과 같은 방법으로 접근하여 코드를 작성할 수 있습니다.

1. 길이가 1인 경우를 초기화합니다.
2. 길이가 2 이상인 경우를 계산합니다.
   • 마지막 자리가 0이면 다음 자리는 1만 가능합니다.
   • 마지막 자리가 9이면 다음 자리는 8만 가능합니다.
   • 그 외의 경우에는 양쪽으로 이동이 가능합니다.
3. 길이가 N인 계단 수의 개수를 모두 합한 후, 나머지 연산을 적용하여 결과를 반환합니다.

MOD = 1000000000

def count_stairs(N):
  # dp[i][j]: 길이가 i이고 마지막 자리가 j인 계단 수의 개수
  dp = [[0] * 10 for _ in range(N + 1)]

  # 길이가 1인 경우, 각 자리에 대해 1로 초기화
  for i in range(1, 10):
    dp[1][i] = 1

  # 길이가 2 이상인 경우 계단 수 개수 계산
  for i in range(2, N + 1):
    for j in range(10):
      if j == 0:
        # 마지막 자리가 0인 경우, 바로 다음 자리는 1만 가능
        dp[i][j] = dp[i - 1][j + 1]
      elif j == 9:
        # 마지막 자리가 9인 경우, 바로 다음 자리는 8만 가능
        dp[i][j] = dp[i - 1][j - 1]
      else:
        # 마지막 자리가 1부터 8까지인 경우, 양쪽으로 이동 가능
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD

  # 길이가 N인 계단 수의 개수를 모두 합한 후 1,000,000,000으로 나눈 나머지 반환
  return sum(dp[N]) % MOD

if __name__ == "__main__":
  N = int(input())
  result = count_stairs(N)
  print(result)