[BOJ/Python] 11057_오르막 수

문제 출처:https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 

문제

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

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

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

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

10

예제 입력 2

2

예제 출력 2

55

예제 입력 3

3

예제 출력 3

220

---

풀이

 

DP를 이용하여 문제를 해결하였다.

오르막 수의 맨 마지막 자리가 0,1,2,3,...,9인 리스트를 생성한다.

한 자릿수인 경우, 0,1,2,3,4,5,6,7,8,9 각각 하나씩 존재하므로 모두 값이 1이다.

이제 한 자리 수를 이용하여 두 자리의 오르막 수를 구하는 경우를 살펴보자.

 

두 자리 수이면서 맨 마지막 자리 (일의 자리)가 0이 될 수 있는 수는 00 뿐이다.

이것은 한 자리 수 리스트 0의 index의 값과 같음을 알 수 있다.

두 자리 수이면서 일의 자리가 1이 될 수 있는 경우는 01과 11이 존재한다.

• 한 자리 수 0 뒤에 1을 붙인 경우
• 한 자리 수 1 뒤에 1을 붙인 경우

즉, 이 두 가지는 한 자리 수의 0의 index의 값과 1의 index의 값을 더한 값이다.

마찬가지로 두 자릿수이면서 일의 자리가 2인 경우는 다음과 같다.

• 한 자리 수 0 뒤에 2를 붙인 경우
• 한 자리 수 1 뒤에 2를 붙인 경우
• 한 자리 수 2 뒤에 2를 붙인 경우

한 자리 수의 index 0의 값 + index 1의 값 + index 2의 값 = 3 임을 알 수 있다.

이를 이용하면 두 자리의 오르막 수를 구할 수 있다.

 

일의 자리가 0,1,2,... 9인 두 자리의 오르막 수를 구하였다.

이제 두 자리의 오르막 수를 이용하여 세 자리의 오르막 수를 구하는 과정은 다음과 같다.

 

일의 자리가 0의 경우 00 뒤에 0을 붙이는 경우밖에 없으니 한 가지뿐이다.

 

일의 자리가 1의 경우는 다음과 같다.

• 두 자리이면서 일의 자리가 0인 수 뒤에 1을 붙이는 경우 1가지
• 두 자리이면서 일의 자리가 1인 수 뒤에 1을 붙이는 경우 2가지

총 3가지가 된다.

일의 자리가 2인 경우는 다음과 같다.

• 두 자리이면서 일의 자리가 0인 수 뒤에 2를 붙이는 경우 1가지
• 두 자리이면서 일의 자리가 1인 수 뒤에 2을 붙이는 경우 2가지
• 두 자리이면서 일의 자리가 2인 수 뒤에 2을 붙이는 경우 3가지

총 6가지가 된다. 이를 이용하여 두 자리의 오르막 수를 구하면 다음과 같다.

 

 

이러한 결과를 통해 다음과 같은 결론을 내릴 수 있다.

• n자리의 오르막 수 리스트를 이용하여 n+1자리의 오르막 수를 구하는 경우 (index 값 = 일의 자리)
• index 0인 n+1자리의 오르막 수 = index 0인 n자리의 오르막 수
• index 1인 n+1자리의 오르막 수 = index 0인 n자리의 오르막 수 + index 1인 n 자리의 오르막 수
• index 2인 n+1자리의 오르막 수 = index 0인 n자리의 오르막 수 + index 1인 n 자리의 오르막 수 + index 2인 n자리의 오르막 수

즉, index 2인 n+1자리의 오르막 수 = index 1인 n+1자리의 오르막 수 + index 2인 n자리의 오르막 수로 표현할 수 있다.

이를 일반화하면 다음과 같은 결론을 내릴 수 있다.

index A인 n+1자리의 오르막 수 = index A-1인 n+1자리의 오르막 수 + index A인 n자리의 오르막 수 (A>=1)

이를 이용하여 n자리의 오르막 수를 이용하여 n+1자리의 오르막 수의 개수를 쉽게 구할 수 있다.

 

코드는 다음과 같다.

 

import sys
 
n = int(sys.stdin.readline())
 
numbers = [1 for _ in range(10)]
 
for i in range(n-1):
    for j in range(1,10):
        numbers[j] = numbers[j-1] +numbers[j]
 
print(sum(numbers)%10007)