[BOJ_Gold 5] 2688 - 줄어들지 않아 [python]

 

2688번: 줄어들지 않아

문제

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

예를 들어, 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자리 수의 개수를 출력한다.

---

Well-Known DP문제인 계단수와 상당히 유사한 문제입니다.

 

주어진 규칙을 만족하는 N자리 숫자에 대해, 뒤에 추가될 수 있는 숫자는 기존 맨 뒷자리 숫자보다

크거나 같은 숫자뿐입니다. 이 성질을 이용해, 다음과 같은 점화식을 생각할 수 있습니다.

 

DP[N][K]는 N자리의, K로 끝나는 수의 경우의 수 라고 할때,
DP[N][K] = SUM(DP[N-1][0~K]) #뒤가 0~K인 수에는 K를 이어붙일 수 있으므로

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

 

 

Bottom - Up

dp = [[0] * 10 for _ in range(66)]
dp[0][0] = 1 #Base는 여기에서 시작한다.
for i in range(1,66):
    dp[i][0] = dp[i-1][0]
    for j in range(1,10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

for i in range(int(input())):
    print(dp[int(input())+1][-1])

 

Top - Down

dp = [[-1] * 10 for _ in range(66)]
dp[0][0] = 1 #Base는 여기에서 시작한다.

def TopDown(n : int, k : int) -> int:
    #n자리수의, k로 끝나는 수
    if n == 0 and k: return 0
    if dp[n][k] != -1: return dp[n][k]

    dp[n][k] = 0
    for i in range(k+1):
        dp[n][k] += TopDown(n-1,i)

    return dp[n][k]

TopDown(65,9)
for _ in range(int(input())):
    print(dp[int(input()) + 1][-1])