[백준] 11057번:오르막 수 (python 파이썬)

Coding - Algo/python

jainn 2021. 4. 6. 00:23

728x90

문제

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수

www.acmicpc.net

난 당연히 맨 앞에 오는 숫자부터 고려를 해주면서 규칙을 찾아보았다.

앞에서부터 하니 규칙은 보이나 규칙을 dp로 정의하기가 어려웠다.

자릿수가 주어졌을 때 맨 뒤에 오는 숫자에 대해 표를 만들어 구해보면 규칙을 쉽게 알 수 있었다.

위와 같이 num[i] += num[i-1] 이라는 규칙이 보인다.

따라서 끝까지 적용해주면 된다.

n = int(input())

num = [1]*10

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

print(sum(num)%10007)