백준 2688번 : 줄어들지 않아 in Python

2688번: 줄어들지 않아

 

www.acmicpc.net

이 문제는 줄어들지 않는 n자리 수의 개수를 구하는 문제이다. 여기서 줄어들지 않는 수란 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같은 수를 말한다.

이는 dynamic programming으로 쉽게 해결할 수 있다. (i+1)자리 수의 맨 앞자리 수가 j일 때 줄어들지 않는 수의 개수를 (i, j) 성분에 저장하는 (n+1)*10 크기의 행렬 dp를 만들고, 초기값으로 dp[0][i] ( i = 0, ... , 9)를 1로 한다. 

그 다음 i가 1일 때부터 n일 때까지 순회하면서 (i+1)자리 수의 줄어들지 않는 수의 개수를 구한다. 줄어들지 않는 수의 개수를 구할 때 맨 앞자리의 수가 j로 정해지면 그 뒤자리에 나올 수 있는 수는 j와 9 사이의 수만 가능하므로 dp[i][j]는 dp[i-1]의 j번째 성분부터 9번째 성분까지 모두 더한 값으로 한다. dp[i-1][k]는 맨 앞자리 수가 k인 수만을 셌음을 보장하기 때문에, 이를 이용해 (i+1)자리 수의 줄어들지 않는 수의 개수를 쉽게 구할 수 있다. 

이제 모든 순회가 끝난 뒤, dp[n][0]은 (n+1)자리 수의 맨 앞자리 수가 0일 때 줄어들지 않는 수의 개수를 저장하는데, 맨 앞자리가 0인 경우 줄어들지 않는 모든 n자리 수를 뒤에 붙일 수 있기 때문에 dp[n][0]는 곧 줄어들지 않는 n자리 수의 개수와 같다. 따라서 dp[n][0]을 출력한다.

이를 코드로 구현하면 다음과 같다.

T = int(input())
dp = [[0]*10 for _ in range(66)]
for i in range(10):
    dp[0][i] = 1
for i in range(1, 65):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] += dp[i-1][k]
for _ in range(T):
    n = int(input())
    print(dp[n][0])