[알고리즘] 백준 11057 파이썬 - 오르막 수

 

11057번: 오르막 수

문제

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

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

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

 

문제풀이

n=int(input())
#01
dp=[1]*10
for i in range(n-1):
	#02
    for j in range(1, 10):
        dp[j] += dp[j-1]
#03
print(sum(dp)%10007)

- #01 : 한 자리수는 모두 오르막 수 이기에 [1]*10을 초기값으로 준다.

- #02 : 두 자리수의 규칙을 확인해보면, 각 자리마다 [1,2,3,4,5,6,7,8,9,10]가 나온다.

           세 자리수는 [1,3,6,10,15,21,28,36,45,55] 즉 dp[j]+=dp[j-1]의 식을 얻을 수 있다.

- #03 : 최종적으로 얻은 dp의 합을 10007로 나눈 나머지 값을 출력한다.