백준 - 줄어들지 않아(2688)

Dynamic Programming

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다.

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

---

0 ~ 9 까지의 숫자를 커버하려면 원소 10개 필요

1자리인 경우
arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] => 총 10개 가능
2자리인 경우
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => 총 55개 가능
3자리인 경우
arr = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] => 총 220개 가능

2자리부터 각 인덱스에 맞는 원소 값은 직전 배열의 그 인덱스까지의 합으로 표현된다. 왜냐면 그 숫자를 포함해 10개의 숫자 중 크거나 같은 수를 카운팅해야 문제 조건을 만족한다. 예를 들면 3이라는 숫자의 앞자리에 오려면 3, 4, 5, 6, 7, 8, 9이므로 10 - 3 = 7(개).

import sys

N = int(sys.stdin.readline())
dp = [1] * 10 # n이 1 때부터 구하기 위한 기본 셋팅

for i in range(N):
    case = int(sys.stdin.readline())
    li = [[0] * 10 for i in range(case)] 
    # n자리수까지 구하려면 1, 2, 3, ... n - 1자리까지 알아야하므로 n개 만큼 [0] * 10으로 초기화
    for j in range(len(li)):
        if j == 0: # 첫째자리의 경우만 처음 선언된 dp 사용
            for x in range(len(li[j])):
                li[j][x] = int((dp[x] * (dp[x] + 1)) / 2) 
        elif j > 0: # 둘째자리부터 직전 자릿값들 더하기
            for x in range(len(li[j])):
                li[j][x] = int(sum(li[j - 1][:x + 1]))
        	# 직전 인덱스의 행에서해당 x까지의 합을 구하면 된다.
            
    print(sum(li[-1])) # 마지막 행의 원소값들을 싹 더한다.
   

1) 1자리, 2자리를 디폴트로 껴놓고 하려니까 자꾸 에러발생 -> 이 경우들도 일반화 시켜줘야 한다.
2) li 값들을 구할 때 나누기가 쓰여서 int로 소숫점을 버려줘야한다. ex) int(220.0) = 220