[백준] 11057 : 오르막 수 (파이썬 / Python)

오르막 수

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

---

코드 1

n = int(input())
d = [[0] * 10 for _ in range(n+1)]

for i in range(10):
    d[1][i] = 1
    
for i in range(2, n+1):
    for j in range(10):
        for k in range(j+1):
            d[i][j] += d[i-1][k]
            
print(sum(d[n]) % 10007)

풀이 1

우선 해당 문제는 2가지의 풀이법으로 풀었으며, 1번째 풀이 방법을 개선하여 2번째 풀이 방법이 도출되었다.

우선 1번째 풀이 방법은 다음과 같은 아이디어로 풀었으며, 이 때 d[자리수][맨 마지막 자리의 수] = 오르막 수의 개수이다.

n = 1인 경우, 수가 0으로 시작할 수 있기 때문에 오르막 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 총 10개이다. 따라서, d[1][i] = 1이 된다.

n = 2의 경우, 맨 마지막 자리 수가 0이면 앞에 올 수 있는 수는 [0], 1이면 [0, 1], ... , 9이면 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]가 올 수 있다. 따라서, d[i][j] += d[i-1][k]와 같은 점화식이 도출되었다. 예를 들어 자리수 i = 3, 맨 마지막 자리 수 j = 5이면, i = 3-1이고, k = [0, 1, 2, 3, 4, 5]까지의 경우의 수를 다 더해주면 되는 것이다.

결과는 주어진 n의 경우의 수 d[n]을 추출하여 sum을 이용하여 더해준 후, 10007로 나눈 나머지를 구해주면 된다.

코드 2

n = int(input())
dp = [1] * 10

for i in range(1, n):
	for j in range(1, 10):
    	dp[j] += dp[j-1]

print(sum(dp) % 10007)

풀이 2

https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-11057-%EC%98%A4%EB%A5%B4%EB%A7%89-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python

길이 N과 맨 뒷 자리수를 기준으로 위와 같은 규칙을 발견할 수 있었다.