백준)11057.오르막수 - 식도출

1년전 이 문제를 풀다가 포기했던 기억이 있다. 그땐 다른 사람들의 풀이를 보아도 왜 그렇게 푸는지 이해를 못했다.
이번에도 역시 바로 풀지는 못했다. 처음에는 브루트포스처럼 수를 올려 일일이 수가 오르막수인지 검사하는 방식으로 풀었다가  Numberformatexception을 만나고 정신을 차렸다.

 

 

이 포스팅은 나처럼 수학 잼병인 사람들을 위한 식 도출과정을 중심으로 작성했다. 

 

도출과정 

두자리 수에서 세자리 수가 되는 과정을 그려봤다.
0부터 9까지 적어두고, 해당 수가 앞자리에 오는 경우를 적었다.

 

 

 

1로 시작하는 두자리의 오르막 수를 예로 들면 11, 12, 13 ... 19가 있다. 
여기서 앞자리에 올 수 있는 수는 0과 1두가지다.==> 001, 012, 013 ... 019
2로 시작하는 두자리의 오르막 수는 22, 23, 24 ... 29가 있다.
여기서 앞자리에 올 수 있는 수는 0,1,2 세가지다.

1로 시작하는 두자리의 오르막 수에 앞자리로 위치할 수 있는 수는 2개(0,1)
2로 시작하는 두자리의 오르막 수에 앞자리로 위치할 수 있는 수는 3개(0,1,2) 
.
.
.
9로 시작하는 두자리의 오르막 수에 앞자리로 위치할 수 있는 수는 10개(0,1,2,3,4,5,6,7,8,9)
이런식으로 증가한다. 

여기서 세자리의 오르막 수의 개수를 유추할 수 있다.
1로 시작하는 두자리의 오르막 수는 11, 12, 13 ...19 로 총9개이며 세자리의 오르막 수를 만들때
이 앞에 0이 위치하는 경우, 1이 위치하는 경우 두가지 경우이므로
9 * 2 = 18개가 도출된다. 
마찬가지로 9로 시작하는 두자리의 오르막 수는 99로 총1개이며 세자리의 오르막 수를 만들때 
이 앞에 0~9가 위치하는 경우를 구해보면
1 * 10 = 10개가 된다. (099,199,299 ... 999)

위와같은 방식으로 두자리의 오르막 수의 개수를 이용해 세자리의 오르막 수의 개수를 구해보면
0인경우 > 10 * 1 = 10
1인경우 > 9 * 2 = 18
2인경우 > 8 * 3 = 24
3인경우 > 7 * 4 = 28
4인경우 > 6 * 5 = 30 
5인경우 > 5 * 6 = 30
6인경우 > 4 * 7 = 28 
7인경우 > 3 * 8 = 24
8인경우 > 2 * 9 = 18
9인경우 > 1 * 10 = 10 
위 수를 모두 합친 220이 세자리의 오르막 수의 개수가 된다. 

이제 세자리의 오르막 수에서 네자리의 오르막 수를 도출해야 하는데
0부터 9까지 시작하는 세자리의 오르막 수가 각각 몇 개씩 있는지 계산을 먼저 해야한다.

9부터 시작하는 세자리의 오르막 수를 예로 보면
앞서 9인경우 계산했던(9인경우 1 * 10 = 10)것으로 099,299~999가 만들어 졌고
이렇게 만들어진 10개는 각기 쪼개져 0으로 시작하는 세자리의 오르막 수 ~ 9로 시작하는 세자리의 오르막 수가 되어야 한다.
따라서 10을 10으로 나누어 0부터 자기자신(9)몫까지 1개씩 나눠줘야 하고
8인 경우에는 앞서 계산했던 18을 9로 나누어 0부터 자기자신(8)몫까지 2개씩 나눠주는 방식으로 0까지 진행한다.

1인경우는 앞서 계산했던 18을 2로 나누어 0부터 1까지 9개씩 나눠줘야한다. 

 

이해하기 쉽게 표로 정리해보면 

 

 

위 표의 1인경우를 보자면, 앞의 계산 과정으로 만들어낸 18가지의 오르막 수중 0으로시작하는 9개의 수는 0으로 시작하는 세자리의 오르막 수에 카운팅 되어야 한다. 

마찬가지로 2인경우를 보면, 앞의 계산 과정으로 만들어낸 24가지의 오르막 수 중 0으로 시작하는 8개의 수는 0으로 시작하는 세자리의 오르막 수로, 1로 시작하는 8개의 수는 1로 시작하는 세자리의 오르막 수로 카운팅 되어야 한다. 

 

0으로 시작하는 오르막수 개수만 보면 아래와 같다. 

 

 

 

 

이런 방법으로 0~9로 시작하는 세자리의 오르막수 개수를 구해보면 아래 표와 같다. 

 

 

 

결국 N으로 시작하는 오르막 수의 개수는 이전 자리의 오르막수 개수를 N~9로시작하는 오르막수 개수 까지 합한 값이다.