백준10844 - 쉬운 계단 수 (DP) python

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

문제는 문제에서 제시된 것처럼 모든 자리의 차이가 1인 계단수의 갯수를 출력하는 문제다.

 

문제 풀이 방식

1 ~ 8까지의 수는 각각 2개의 수 (예를 들어 1의 경우 0과 2가 다음에 올 수 있는 계단수)를 가진다고 할 때, 0과 9는 각각 1과 8밖에 계단수를 갖지 못한다는 점으로 점화식을 수립하여 로직을 구현했다. 

단 1의 자리 수의 경우는 먼저 0이 올 수 없으므로 이 점만 유의하면 된다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  N = int(data[0])
  dp = [[0] * 10 for _ in range(N)]
  for i in range(9) :
    dp[0][i+1] = 1

  for i in range(1, N) :
    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]

  result = sum(dp[-1]) % 1000000000
  print(result)

solution(input_data)