[백준 2688 줄어들지 않아] - 파이썬 풀이 🦄

• 백준 2688 줄어들지 않아 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 2688 줄어들지 않아 - 파이썬 풀이 🦄

문제

왼쪽의 Digit이 항상 오른쪽보다 작은 경우의 수를 찾는 문제이다.

Keypoints

• 왼쪽의 수가 주어졌을 때, 오른쪽에 하나를 더 붙이는 수를 생각한다.
• XXX4 -> 4,5,6,7,8,9 6개를 붙일 수 있음.

Solution

def construct_dp(n):
    store_count = [[1 for i in range(10)]]
    for i in range(1,n):
        count_per_digit = [0 for i in range(10)]
        for digit in range(0, 10):
            count_per_digit[digit] = sum(store_count[i-1][:digit+1])
        store_count.append(count_per_digit)
    return store_count

num_test_case = int(input())
targets = [int(input()) for i in range(num_test_case)]
stored_counts = construct_dp(max(targets))

for number in targets:
    print(sum(stored_counts[number-1]))

References

Problem Link