%2021. 11. 11. 19:53에 작성된 글입니다%
https://www.acmicpc.net/problem/1196
1196번: 잭 바우어
첫째 줄에 N과 K가 주어진다. N은 1018보다 작거나 같은 자연수이고, K는 N보다 작거나 같은 자연수이다.
www.acmicpc.net
\(H_n=\sum _{k=1}^n\frac{1}{k}\)
\(f\left(n,\ k\right)=N\left(H_n-H_{n-k}\right)\)
\(f(n, k)\)가 문제를 풀기 위해 코딩해야 하는 함수인데...
naive하게 구현하면 시복도 \(O(N)\)이 나올 것이고 \(N\)의 범위는 \(10^{18}\) 이하 자연수니까 무리 없이 \(T\ L\ E\)를 받아낼 수 있으리라...
분명 근사가 가능할 것 같아서 찾아봤더니 있다.
\(H_n\approx \log n+\gamma +\frac{1}{2n}-\sum_{k=1}^{\infty }\frac{B_{2k}}{2sn^{2s}}\)
\(\gamma=\displaystyle \lim_{n \to \infty}{\left(\sum _{k=1}^n\frac{1}{k}-\ln \left(n\right)\right)}\approx 0.57721566490153286060651...\)
감마는 오일러-마스케로니 상수다. 저건 그냥 소수점 아래 50자리까지 긁어와서 때려박았다.
베르누이 들어간 시그마 부분은 전체 결과에 크게 영향을 미치지는 않는 것 같아서 한 \(k=15\)까지만 넣어줬다.
그리고 일단 근사니까 n이 작은 경우에는 무지막지한 오차가 날 테니까
\(n\)이 작은 경우에는 naive하게 구현하고, 그 이상으로는 근사를 쓰기로 했다.
처음에는 경계를 \(10^7\)로 정했는데 TLE가 나길래 \(10^6\)으로 내렸다.
이제 저걸 구현한 뒤에(Python Decimal 사랑해요)
TLE가 난다 -> Decimal의 precision을 낮추거나 직접 구하기/근사하기의 경계를 조정한다.
precision은 처음에 300으로 시작했다가 50까지 내려서 맞았다. 생각해보니 왜 굳이 300씩이나 잡았을까 싶다.