BOJ 2688 - 줄어들지 않아

문제

N자리 수 중 줄어들지 않는 수(각 자리가 이전 자리 이상)의 개수를 구하라. 0으로 시작하는 수도 포함한다.

입력

테스트 케이스 수와 각 N이 주어진다.

출력

각 N에 대해 줄어들지 않는 N자리 수의 개수를 출력한다.

예제

입력	출력
`1` `3`	`220`

풀이

DP로 각 자릿수에서 시작할 수 있는 경우의 수를 누적한다.

dp[j] = 현재 자리에서 숫자 j로 시작하는 줄어들지 않는 수의 개수
처음에 모든 dp[j] = 1로 초기화한다
각 자리마다 dp[j] = sum(dp[j:])로 갱신한다 (j 이상인 수로 이어지는 경우)

핵심 아이디어: 각 자릿수에서 현재 숫자 이상인 다음 숫자만 선택할 수 있으므로, 접미사 합으로 경우의 수를 계산한다.

코드

for i in range(int(input())):
    n = int(input())
    dp = [1 for i in range(10)]
 
    for i in range(n-1):
        for j in range(10):
            dp[j] = sum(dp[j:])
    print(sum(dp))

복잡도

시간: O(N²)
공간: O(N)

문제