[BOJ/Python] 2688. 줄어들지 않아

📌 문제

https://www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

 

📌 문제 접근 방법

1. 함수를 만들어주고 n이 1일 경우, 0부터 9까지의 한 자리 수만 만들어지기에 바로 10을 리턴해줬다.
2. cnt라는 딕셔너리를 만들어주고 n이 2일 경우를 초기값으로 지정해줬다.
   key값은 맨 앞자리 수이고, value값은 key가 맨 앞자리 수일 경우 만들 수 있는 숫자의 경우의 수이다.
   예를 들어 맨 앞자리 수가 0이라면, 00, 01, 02, ..., 09까지 10개를 만들 수 있다.
3. n-2만큼 반복하게 for문을 만들어줬다. (cnt의 기준이 n이 2일 경우이기 때문)
   다시 0부터 9까지 순회하면서 해당 숫자가 맨 앞자리일 경우의 수를 result에 저장했다.
   예를 들어 n이 3일 경우에 맨 앞자리가 0이라면, n이 2일 경우에서 맨 앞자리가 0~9인 경우를 모두 더해준다.
   맨 앞자리가 9라면, n이 2일 경우에서 맨 앞자리가 9인 경우만 더해준다.

 

📌 코드

# 백준 2688 줄어들지 않아

def counting(n):
    if n == 1:
        return 10

    cnt = {
        0: 10, 1: 9, 2: 8, 3: 7, 4: 6,
        5: 5, 6: 4, 7: 3, 8: 2, 9: 1
    }

    result = {}

    for _ in range(n-2):
        for num in range(10):
            temp = 0
            for t in range(num, 10):
                temp += cnt[t]

            result[num] = temp
        
        cnt = result
        result = {}
    
    return sum(cnt.values())


for _ in range(int(input())):
    n = int(input())

    print(counting(n))