11057. 오르막 수

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 

오르막 수는 수의 자리가 오름차순을 이루는 수. 

인접한 수가 같아도 오름차순으로 친다.

그리고 이 문제는 0으로 시작할수 있다.

 

n = 1 일때

0

1

2

...

9

 

n = 2 일때

01, 02, ... 09  // 9개

12, 13, ... 19 // 8개

23, 24, ... 29 // 7개

...

89             // 1개

 

나는 이차원 배열의 첫번 째 인덱스를 수의 길이, 두 번째 인덱스를 수의 첫자리로 사용했다.

위에서 보면 n = 1일때 0이고 n = 2일때는 0뒤에 0보다 큰 값들 (오르막수이기 때문에)이 올 수 있으므로 

01, 02, ... 09가 되고 총 9개다.

 

n = 1일때 1이면 뒤에 1 보다 큰 수들이 올 수있고 n = 2 일때 12, 13, ... 19 가 되고 총 8개다.

이렇게 앞자리가 1씩 커질수록 뒤에 올 수 있는 수의 개수가 1씩 적어진다. 

d = [[0] * 10 for i in range(1001)]  # 1001 x 10

for i in range(10):  # base
    d[1][i] = 1


def dp(a, b):
    for i in range(9, b - 1, -1):
        d[a][b] += d[a - 1][i]

    return d[a][b]


n = int(input())  # input

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

res = 0
for i in range(10):
    res += d[n][i]

print(res % 10007)

n = 1일때는 어처피 두 번째 인덱스는 상관없이 모두 1가지만 있을수 있으므로 d[1]은 다 1로 채운다.

 

for문이 돌면서 dp함수를 호출해서 d[][]를 채운다. 

예를들어 n = 2이면,

d[2][0]에는 d[1][9], d[1][8] ... d[1][0]이 더해져 9가되고,

d[2][1]에는 d[1][9], d[1][8] ... d[1][1]이 더해져 8이 된다.

---

Solution

 

d[n] : 길이가 n 자리인 수 중에서 오르막수의 총 개수

 

이 문제도 숫자의 마지막 자리의 수가 몇인지가 중요하다.

그래서 d[n][k]에서 n은 길이, k는 마지막 자리의 값으로 둔다.

 

그래서 우리가 구하는 값은 

d[n] = d[n][0] + d[n][1] + ... + d[n][9]

 

 

중요한 것은 d[n][k] 에서 k 값이 d[n-1][i]의 i 값보다 크거나 같아야 '오르막 수' 가 된다는 것이다. 

즉 d[n][k] = d[n-1][0] + d[n-1][1] + ... + d[n-1][k]

 

d = [[0] * 10 for a in range(1001)]
for a in range(10): d[1][a] = 1  # 길이 1일때는 모두 1
mod = 10007

n = int(input())
for i in range(2, n+1):
    for k in range(10):
        for j in range(k + 1):
            d[i][k] += d[i-1][j]
            d[i][k] %= mod  # 배열에 넣을때부터 애초에 10007 나머지 넣는다

sum = 0
for i in range(10): sum += d[n][i]