[BOJ/백준] 11057번 오르막 수 (Python 파이썬)

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

11057번: 오르막 수

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	44236	21615	16705	47.658%

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

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

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1 

10

예제 입력 2 

2

예제 출력 2 

55

예제 입력 3 

3

예제 출력 3 

220

 

---

풀이

문제를 보았을 때 직관적으로 패턴이 떠오르지 않아 자리수 별로 각 경우의 수를 직접 구해보았습니다.

수는 0으로 시작할 수 있다. (조건)
    0 1 2 3 4 5 6 7 8 9(1의 자릿수)
1    1 1 1 1 1 1 1 1 1 1
2    1 2 3 4 5 6 7 8 9 10
3    1 3 6 10 15 21 28 37 47
.
.
.

=> 규칙 : n자리 수에서 k로 끝나는 수의 개수 = n-1의 자리에서 0~k까지 더하기

이를 직접 나열하면 아래와 같다.

######2자리
00 = 1
01 11 = 2
02 12 22 = 3
.
.
.
.

######3자리
000 = 1

001 011 = 1 + 2
111

002 012 022 = 1 + 2 + 3
112 122
222

003 013 023 033 = 1 + 2 + 3 + 4
113 123 133
223 233
333

004 014 024 034 044 = 1 + 2 + 3 + 4 + 5
114 124 134 144
224 234 244
334 344
444

.
.
.
.

####4자리

0004 0014 0024 0034 0044 
0114 0124 0134 0144
0224 0234 0244
0334 0344
0444

1114 1124 1134 1144
1224 1234 1244
1334 1344
1444

.
.
.

즉, n의 자릿수의 경우, 1의 자리에 k가 나오는 경우의 수(k = 0 ~ 9)는,  n-1의 자릿수에서의 0부터 k-1까지의 경우의 수를 모두 더한 것입니다. 제가 위에 적어둔 패턴을 보시면 이해가 편할 것입니다.

따라서 이를 그대로 구현하면 되는데, 매우 쉽게 작성할 수 있습니다.

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0 for i in range(10)] for j in range(n+1)]

# 1의 자릿수 초기화
for x in range(10):
  dp[1][x] = 1
  
for i in range(2, n+1): # i번째 자릿수
  for k in range(10): # 0~9
    temp = 0
    for s in range(0, k+1): # i-1자리 수에서 0~k까지 더하기
      temp += dp[i-1][s]
    dp[i][k] = temp

result = 0
for i in range(10):
  result += dp[n][i]
print(result%10007)