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

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

11057번: 오르막 수

Problem

• 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.
• 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오

조건

• 인접한 수가 같아도 오름차순으로 친다.
• 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
• 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
• 수는 0으로 시작할 수 있다.

SOL

길이가 N인 오르막의 개수, 즉, 길이가 변수이다.

길이가 1일 때

• 0 1 2 3 4 5 6 7 8 9 => 10개

길이가 2일 때

• 00 01 02 03 04 05 06 07 08 09 =>10개
• 11 12 13 14 15 16 17 18 19 =>9개
• 22 23 24 25 26 27 28 29 =>8개 .. 
• 이런 식으로 해서 55개이다.

Bottom up 즉, 하나씩 테이블을 채워가는 방법도 좋지만, 좀 원리적으로 생각하기 위해서, Top down 형식으로, 생각을 해보자.

 

• 마지막 자리의 숫자를 N,길이가 L이라고 하자.
• 그렇다면, 길이가 L, 마지막 자리의 숫자가 N인 오르막 수는 아래와 같은 식을 가지게 된다.
• F(L,N) = F(L-1,N) +F(L-1,N-1) ...F(L-1,0)
• 예를들어,  F(2,5) = F(1,5) +F(1,4) +F(1,3) +F(1,2) +F(1,1) + F(1,0) 으로 생각할 수있다. 직접적으로 구해보자면,     L= 2, N =5 인 오르막 수는 , 05,15, 25,35,45,55가 있을거다.

즉, 점화식이 쉽게 구해졌다. 

하지만, 점화식을 보면 알겠지만, 더 하는 횟수가 너무 많고, calling 하는 함수가 아주 많다.

 

(메모이제이션으로 기록을 하면서 calling 할거지만, 여기서 더 줄여보자)

 

• F(L,N-1) = F(L-1,N-1)+F(L-1,N-2) .......F(L-1,0)
• F(L,N) = F(L-1,N) +F(L,N-1) 로 표현 가능하다.

즉 , F(2,5) = F(1,5) + F(2,4)로 표현이 가능하다는거다! 아주 획기적으로 줄어든다!

• F(L,N) = F(L-1,N) +F(L-1,N-1) ...F(L-1,0) 꼴이 나올 때는,  F(L,N) = F(L-1,N) + F(L,N-1)의 꼴을 의심해보자!

그리고, 이렇게 나타내면 장점이, DP table에 기록하기 매우 쉬워진다.

배열은 random access (임의접근)으로 아주 빠르게 접근하는데, 그 전의 배열의 합을 구하는 것보다, 하나의 인덱스를 접근하는게 훨씬 빠르다.

 

N = int(input())

DP=[[0]*10 for _ in range(N+1)]

DP[1] = [1]*10

for i in range(2,N+1):
	DP[i][0] =1 #n자리 0으로 끝나는 오르막 수는 0000 과 같은 수 1개밖에 없음
	for k in range(10):
		DP[i][k] = DP[i-1][k]+DP[i][k-1]

print(sum(DP[N]) %10007)