BOJ 9764 - 서로 다른 자연수의 합 (Python3)

사실 이번 게시글은 자기성찰성이 깊은 게시글이다. 수학 원툴에서 쓸 수 있는 도구를 다변화시킬 필요가 있어서 우선 dp를 연습하기로 하고 골드 범위 내에서 랜덤으로 뽑기를 반복했는데, dp 문제임을 알고 있어도 dp로 못 접근한 문제가 있기 때문이다. 이게 그렇고, 다른 것도 하나 있는데...

하여튼 생각해보다가 안 되니 아득하게 높은 레벨의 풀이를 정말 억지로 끌고 와서 겨우겨우 풀어냈다. 닭 잡는 데 핵폭탄을 떨어트린 느낌이라고 해야 하나...

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

양의 정수 $N$ $(1\le N\le 2000)$을 서로 다른 자연수의 합으로 나타내는 방법은 여러 가지가 있다.

예를 들어, $N=5$인 경우 $N=5=2+3=1+4$로 총 3가지 방법이 있다. $1+1+3$에서 1은 여러 번 등장하기 때문에 세지 않고, $2+3$과 $3+2$는 순서만 바뀐 것이기 때문에 같은 것으로 센다.

또, $N=6$인 경우에는 $N=6=1+5=2+4=1+2+3=2+4$로 총 4가지 방법이 있다.

$N$이 주어졌을 때, 서로 다른 자연수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에, 테스트 케이스의 개수 $T$ $(1\le T\le 20)$이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, $N$이 주어진다.

 

예제 입력)

4
5
6
10
200

 

출력

각 테스트 케이스마다 $N$을 서로 다른 자연수의 합으로 나타내는 방법의 수를 $100999$로 나눈 나머지를 출력한다.

 

예제 출력)

3
4
10
50568

 

---

내 코드

import decimal
def fft(a, b, digit = 0):
    """by teferi"""
    decimal.setcontext(
        decimal.Context(prec=decimal.MAX_PREC, Emax=decimal.MAX_EMAX))
    if digit == 0:
        digit = min(20, len(str(min(len(a), len(b)) * max(a) * max(b))))
    f = f'0{digit}d'
    a_dec = decimal.Decimal(''.join(format(x, f) for x in a))
    b_dec = decimal.Decimal(''.join(format(x, f) for x in b))
    c_dec = a_dec * b_dec
    total_digit = digit * (len(a) + len(b) - 1)
    c = format(c_dec, f'0{total_digit}f')
    return [int(c[i:i + digit]) for i in range(0, total_digit, digit)]
ans = [1]
for i in range(1,2001):
    temp = [1] + [0]*i; temp[-1] = 1
    ans = fft(temp,ans)[:2001]
    ans = [i%100999 for i in ans]
for _ in range(int(input())): print(ans[int(input())])

 

골드 하위 dp문제를 푸는 데 생성함수와 FFT를 가져온 사람의 꼬라지를 보라.

 

서로 다른 자연수의 합의 생성함수는 다음과 같다.

$$\text{gf}(x)=\prod _1^{\mathrm{\infty }}(1+x^i)$$

그러므로 $N$을 서로 다른 자연수의 합으로 나타내는 방법의 수는 저 생성함수의 $N$차항 계수와 동일하다는 것이다.

서로 다른 자연수의 합이고 $N$의 제한이 2000보다는 크지 않으니, $\prod _1^{2000}(1+x^i)$로 생성함수를 두고 풀어도 된다. 그리고 이 2000이라는 제한이 굉장히 작으므로, 전부 깡으로 곱해버리는 형식으로 풀이를 시도해도 시간 안에 들어오게 된다. 물론 다항식의 곱은 FFT를 사용한다.

이게 과연 올바른 풀이일지는 잘 모르겠다. 모로 가도 통과만 하면 된다가 모토기는 했는데, dp 실력을 올리겠답시고 한 연습에서 머리를 쥐어뜯다가 이런 식으로 뭉개고 들어가는 식의 풀이는... 그닥 마음에 들지는 않는다.

 

이로서 9764번의 풀이를 마친다.