문제
문제 : https://www.acmicpc.net/problem/11057
오르막 수란 수의 자릿수가 오름차순을 이루는 수를 말한다. 이때 인접한 두 수의 값이 같아도 오름차순을 준수하는 것으로 판단한다.
예로 들어 2234, 3678, 1119은 오르막 수이다. 하지만 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때 오르막 수의 개수를 구하여라. 수는 0으로 시작할 수 있다. 단, 결괏값은 10007로 나눈 수로 출력한다.
+ 다른 사람의 풀이를 참고했다.
접근
동적 계획법으로 접근하면 좋은 문제다.
수의 길이가 1인 경우, 오르막 수는 0, 1, 2, 3 …… 9가 해당된다.
수의 길이가 2인 경우, 첫번째 자리의 수에 따라 다음으로 올 수 있는 수의 개수는 다음과 같다.
| 자리 수 | 다음 자리 수 | 개수 |
| 0 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 | 10 |
| 1 | 1, 2, 3, 4, 5, 6, 7, 8, 9 | 9 |
| 2 | 2, 3, 4, 5, 6, 7, 8, 9 | 8 |
| 3 | 3, 4, 5, 6, 7, 8, 9 | 7 |
| … | … | … |
수의 길이가 3인 경우, 첫번째 자리의 수에 따라 다음으로 올 수 있는 수의 개수는 아래와 같다.
| 자리 수 | 다음 자리 수 |
| 0 | 00, 01, 002, …, 88, 89, 99 |
| 1 | 11, 112, 13, …, 88, 89, 99 |
| 2 | 22, 23, 24, …, 88, 89, 99 |
| 3 | 33, 34, 35, …, 88, 89, 99 |
| … | … |
즉, 수의 길이가 2인 오르막 수의 개수를 참조하여 계산할 수 있다.
예로 들어 수의 길이가 3이고 첫 번째 자리 수가 0인 오르막 수의 개수는 수의 길이가 2이고 첫번째 자리의 수가 0 이상 9 미만인 오르막 수의 총 개수이다.
수의 길이와 첫번째 자리 수에 따라 오르막 수의 개수를 표로 표현하면 아래와 같다.
이 점을 이용해 memoization으로 문제를 해결할 수 있다.
풀이
1. 메모이제이션에 사용할 테이블 초기화
인덱스가 자리의 수라고 가정하고, 수의 길이가 1인 오르막 수의 개수로 초기화했다.
memo = [[1 for i in range(10)]]
2. 나머지 연산에 사용할 수 선언
divided = 10007
3. 수의 길이 초기화
n = int(sys.stdin.readline())
4. 오르막 수 계산
각 자리 수의 오르막 수의 개수를 계산한다. 계산한 결과는 나머지 연산하여 저장하고 해당 연산은 테이블의 길이가 수의 길이와 동일해질 때까지 반복한다.
memo.append([sum(memo[-1][i:]) % divided for i in range(10)])
5. 결괏값 출력
마지막 테이블 원소의 합을 나머지 연산한 뒤 출력한다.
print(sum(memo[-1]) % divided)
전체 코드는 아래와 같다.
import sys
memo = [[1 for i in range(10)]]
divided = 10007
n = int(sys.stdin.readline())
for i in range(1, n):
memo.append([sum(memo[-1][i:]) % divided for i in range(10)])
print(sum(memo[-1]) % divided)
참고 문서
https://minhamina.tistory.com/147