이번 문제는 백준 실버 1 문제인 오르막 수 문제이다.
문제를 차근차근 한 번 살펴보자.
2234, 34567과 같이 수의 크기가 계속 올라가는 수를 오르막수라고 한다.
또한, 길이가 N으로 주어지는데 N의 제한이 1000까지이다.
1000자리의 수..? 사실상 이걸 직접 구현해서 구한다는 것은 말이 안된다.
직관적으로 누구나 바로 알 수 있는 사실일 것이다.
그럼 우리는 어떻게 구할 수 있을까? 생각해보자.
한 자리 오르막 수는 뭐가 있을까?
0, 1, …, 9까지 총 10개가 있을 것이다.
그럼 두 자리 오르막 수는?
11, 12, 13, …, 19, .. 22, 23,24, … 와 같이 계속 진행될 것이다.
세 자리는 111, 112, 113, .. , 122, … 와 같이 진행될 것인데,
적다보니 뭔가 이용할 수 있는 부분이 보이는 것 같다.
두 자리 오르막 수를 관찰해보면, 첫 자리가 모두 오르막 수이다.
즉, 한 자리 오르막수 뒤에 한 자리 오르막수를 붙여 두 자리를 만든 것이다.
이 점을 규칙으로 뭔가 해답을 찾을 수 있을 것 같다.
그럼 두 자리 오르막수 뒤에 오르막수들을 붙이면, 세 자리 오르막수가 될 것이다.
앞에서 계산한 결과를 다음 계산에 동일하게 이용한다?
이것은 우리가 흔히 말하는 DP(동적 프로그래밍) 의 개념이다.
DP!
그럼 한 자리 오르막수의 개수를 두 자리수에 어떻게 이용할까?
0 뒤에는 0 이상의 수 10개의 수가 올 수 있다.
1 뒤에는 1 이상의 수 9개의 수가 올 수 있다.
2 뒤에는 2 이상의 수 8개가 올 수 있다…
위와 같이 계속 생각해보면, 10 + 9 + 8 + .. + 1 = 55개가 될 것이다.
그럼 세 자리수는?
0 뒤에는 00 01 02 03… 11… 99 까지 55개의 수가 올 수 있다.
1 뒤에는 00 01.. 을 제외한 11.. 부터 99까지 45개의 수가 올 수 있다.
2 뒤에는 22.. 부터 99까지 36개의 수가 올 수 있다.
규칙이 이제 보인다!
그럼 네 자리수는
0 뒤에는 (55 + 45 + … + 1) 만큼의 수가 올 수 있을 것이며,
1 뒤에는 (45 + 36 + .. + 1) 만큼의 수가 올 수 있을 것이다.
따라서 결국, 우리는 가장 작은 9로 시작하는 오르막 수 부터
각 자리수 별로 이전 단계의 결과와 현재 단계의 이전 수를 더해가면 된다.
자세히 말하면, 8로 시작하는 세 자리수 오르막 수는?
9로 + 8로 시작하는 두 자리수 오르막 수
7으로 시작하는 세 자리수 오르막 수는?
9로 + 8로 + 7로 시작하는 두 자리수 오르막 수
위와 같이 오르막 수의 개수를 구해나갈 수 있으므로,
현재 수로 시작하는 이전 단계의 오르막수 와,
이전 수로 시작하는 현재 단계의 오르막수 두 가지를 더해주게 되면,
결국 마지막 원하는 자리의 전체 오르막 수를 구하는 점화식이 된다.
DP는 한 번에 생각이 안나는 경우가 많다.
그럴 땐 이번 문제를 푼 것처럼 모든 경우를 다 직접 적어보자.
규칙을 찾게 되고, 점화식을 찾는다면 문제는 술술 풀릴 것이다.