쉬운 계단 수 [백준 10844] - python

import sys
input = sys.stdin.readline
mod_num = 1_000_000_000

def BOJ10844() :
  n = int(input())
  dp = [[0 for _ in range(10)] for _ in range(101)]
  dp[1] = [0] + [1 for _ in range(9)]
  
  for i in range(2, 101) :
    for j in range(10) :
      if j == 0 :
        dp[i][j] = dp[i-1][1] % mod_num
      elif j == 9 :
        dp[i][j] = dp[i-1][8] % mod_num
      else :
        dp[i][j] = (dp[i-1][j-1] % mod_num + dp[i-1][j+1] % mod_num) % mod_num

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

BOJ10844()

 

계단수 1에서 만들수 있는 숫자는 10과 12입니다.

계단수 8에서 만들수 있는 숫자는 87과 89입니다.

계단수 9에서 만들수 있는 숫자는 98 입니다.

계단수 10에서 만들수 있는 숫자는 101 입니다.

 

 

끝자리가 0과 9인경우 만들수 있는 계단수는 각각 1개씩 그 외의 끝자리 수들은 2개씩 만들수 있습니다.

n자리수의 계단수 개수는 n-1 자리수에서 계단수들의 끝자리에 영향을 받으므로 dp를 선택하였습니다.

아래의 그림을 보면 이해가 빠를수 있습니다.

 

 

끝자리 0을 만들수 있는건 이전 자리수의 끝자리 1입니다,.

끝자리 4를 만들수 있는건 이전 자리수의 끝자리 3과 5 입니다.

끝자리 9를 만들수 있는건 이전 자리수의 끝자리 8입니다,.

 

이런식으로 개념을 잡고 차근차근 문제를 접근하시면 해결하실수 있으실 겁니다!

 

 

 

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

10844번: 쉬운 계단 수