[백준 11057 파이썬/python] 오르막 수

오르막 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	47049	23005	17798	47.720%

문제

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

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

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

입력

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

출력

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

예제 입력 1

1

예제 입력 2

2

예제 입력 3

3

예제 출력 1

10

예제 출력 2

55

예제 출력 3

220

풀이

1) DP

n = int(input())
mod = 10007
d = [[0] * 10 for _ in range(1001)]
# i : 숫자 길이, j : 현재 마지막 숫자, k : 이전 마지막 숫자
for i in range(10):
    d[1][i] = 1

for i in range(2, n + 1):
    for j in range(10):
        for k in range(j + 1):
            d[i][j] += d[i - 1][k]

ans = sum(d[n])
print(ans % mod)

1. n을 입력받습니다.

2. mod 값을 10007로 설정합니다.

3. d라는 1001 x 10 크기의 2차원 리스트를 생성하고 모든 원소를 0으로 초기화합니다.

4. 길이가 1인 경우, 모든 숫자는 자신이 마지막 숫자인 오름차순숫자이므로 d[1][i] = 1로 설정합니다.

5. 길이가 2 이상인 경우, 숫자 길이 i와 마지막 숫자 j에 대해 다음을 수행합니다.
   • 마지막 숫자가 j인 경우, 이전 숫자는 j 이하의 숫자이어야 합니다. 따라서 이전 마지막 숫자 k의 범위를 0부터 j까지 설정합니다.
   • 길이가 i-1인 비내림차순 숫자의 개수인 d[i-1][k]를 모두 더해 d[i][j]에 누적합니다.

6. 마지막으로, 길이가 n인 오름차순 숫자의 개수를 모두 더한 후 mod 값으로 나눈 나머지를 출력합니다.

2) 숏코딩

import math
print(math.comb(9+int(input()),9)%10007)

math.comb 함수는 조합(combination)을 구하는 함수로, n개 중에서 r개를 선택하는 경우의 수를 구합니다.

이 문제에서는 길이가 N인 오르막 수의 개수를 구하는 것이므로, 각 자리 수가 0부터 9까지의 숫자 중에서 선택되어야 합니다. 따라서, 첫 번째 자리부터 N번째 자리까지 모두 0부터 9까지의 숫자 중에서 선택할 수 있으므로, math.comb 함수를 이용하여 오르막 수의 개수를 구할 수 있습니다. 위 코드에서, math.comb(n+9, 9)는 0부터 9까지의 숫자 중에서 n개를 선택하는 경우의 수를 계산합니다. 이는 길이가 n인 오르막 수의 개수와 같으므로, 이 값을 10007로 나눈 나머지를 출력해주면 됩니다.

Uploaded by N2T