白駿-減らない(2688)

Dynamic Programming

質問する

ある数字が減少しないとは、左の桁数がその数字の各桁数以下であることを意味します.
たとえば、1234は減少しません.
減少しない4桁を例にとると、0011、1111、1112、1122、2223がある.減少しない4桁は715個.
この問題では、数字の前にゼロ(leading zero)があります.4桁は正しくありません.
nが与えられた場合、nビット数が減少しないようにプログラムを作成してください.

入力

第1行は、試験例の個数T(1<=T<=1000)を与える.各テストボックスは、1つの数字nで構成されています.(1 <= n <= 64)

しゅつりょく

各試験例について、1行の減少しない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