오르막 수[백준 11057] - python

import sys
input = sys.stdin.readline
mod_num = 10_007

def BOJ11057() :
  n = int(input())
  dp = [[0 for _ in range(10)] for _ in range(n+1)]
  dp[1] = [1 for _ in range(10)]
  
  for i in range(2, n+1) :
    for j in range(10) :
      dp[i][j] = sum(dp[i-1][:j+1]) % mod_num
  
  print(sum(dp[n]) % mod_num)

BOJ11057()

 

접근 방법 :

1. dp는 끝자리가 i 인 숫자의 개수를 나타내는 배열이다.

2. 끝자리 i를 만들수 있는 숫자는 dp[n-1]의 끝자리 i 까지의 숫자들의 합이다.

 

1자리 수 만들수 있는 2자리 수 끝자리 0 은 00 

1자리 수 만들수 있는 2자리 수 끝자리 1 은  01, 11

1자리 수 만들수 있는 2자리 수 끝자리 2 은  02, 12, 22

1자리 수 만들수 있는 2자리 수 끝자리 3 은  03, 13, 23, 33

 

~~~

 

1자리 수 만들수 있는 2자리 수 끝자리 9 은  09, 19, 29, 39, 49, 59, 69, 79, 89, 99

 

이전 인덱스의 자신보다 같거나 작은 숫자들에서 만들수 있으므로 그들의 합을 더해주면 된다.

 

 

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

11057번: 오르막 수