[백준 11057 : PYTHON] 오르막 수

문제 풀기 : 11057번

11057번: 오르막 수

문제

오르막 수는 수의 자리가 오름차순을 이루는 수.

인접한 수가 같아도 오름차순으로 친다.

 

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하라.

 

수는 0으로 시작할 수 있다.

문제풀이

DP 테이블을 2차원 배열로 만든다.

dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에 올 수 있는 일의 자리 수 ]

→ 뒤에 오는 숫자를 기준으로 앞에 올 숫자의 경우의 수를 따져준다.

 

n = 2  자리수 일 경우

0 앞에 올 수 있는 수는 0

1 앞에 올 수 있는 수는 0, 1

2 앞에 올 수 있는 수는 0~2

.

.

.

9 앞에 올 수 있는 수는 0~9

 

n = 3 일 경우에도 같은 방식으로 n = 2의 경우의 수를 더해준다.

 

1 자리 수일 때는 1로 초기화 해주고 시작한다.

dp[1][i] = 1

전체코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0] * 10 for _ in range(n + 1)]
# 1 자리수는 1로 초기화(앞에 0 올 수 있음)
for i in range(10):
    dp[1][i] = 1

for i in range(2, n+1): # 자리 수
    for j in range(10): # 뒤에 있는 숫자
        for k in range(j+1): # 앞에 올 숫자
            dp[i][j] += dp[i-1][k]

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