[Seop's의 코드풀이] 백준 2688 줄어들지 않아 - Python

이번에 풀어볼 문제는 백준 2688번 문제인 '줄어들지 않아' 라는 문제입니다.

문제는 다음과 같습니다.

 

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

2688번: 줄어들지 않아

 

줄어들지 않는 수를 각각 구하게 된다면 시간초과가 발생할 것입니다. 64자리까지 있으니까 말이죠

그렇다면 각 자릿수의 경우들간의 관계를 살펴보면 좀 더 쉽게 풀 수 있을 것 같습니다.(다이나믹 프로그래밍을 사용했습니다.)

 

먼저 자리수에 따른 경우의 수를 살펴보면 다음과 같습니다.

1의 자리수 중 줄어들지 않는 수는 모든 수가 가능하므로 10개 입니다.

2의 자리수 중에서는 앞자리가 0일때 10개부터 시작해서 10 + 9+ ... 를 진행하면 55개가 됩니다.

3의 자리수 부터는 뭔가 규칙이 보이기 시작합니다. 2의 자리수의 총 경우의 수 가 3의 자리수 중에서 0으로 시작하는 경우의 수 입니다.

그 이후부터는 위의 수를 하나씩 빼면 되어 보입니다. 말로는 표현하기 좀 힘드니 사진으로 보여드리겠습니다.

이제 좀 감이 잡히시나요? 

이런식으로 64자리수 까지의 경우의 수를 모두 구해봤자 640번만 반복하면 되기 때문에 시간적으로 굉장히 여유롭습니다.

 

전체적인 코드는 다음과 같습니다.

질문과 피드백은 언제나 감사드립니다.

 

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    T = int(input())
    num = dict()
    num[1] = [[1,1,1,1,1,1,1,1,1,1], 10]
    num[2] = [[10,9,8,7,6,5,4,3,2,1], 55]
    for i in range(3, 65) :
        cnt = num[i-1][1]
        num[i] = [[]]
        for j in num[i-1][0] :
            num[i][0].append(cnt)
            cnt -= j
        num[i].append(sum(num[i][0]))
    for _ in range(T) :
        temp = int(input())
        print(num[temp][1])