BOJ 13294 - 역팩토리얼 (Python3)

각종 프로젝트로 인생이 바빠져서 블로그 관리를 전혀 하지 못했다. 복수전공 승인, 수강신청, 동아리 활동, SUAPC 출전... 이제 막 100일을 찍은 초보 코더의 삶에 이리 많은 일이 벌어질 줄이야.

오랜만에 귀엽고(?) 재미있는 수학 문제를 발견했다. 인터넷에 풀이도 거의 없더라. 난이도만큼의 값을 하지만, 배경지식이 없으면 난항에 빠질 것 같은 문제다.

풀이방법이 각양각색이지만, 이 포스트에 적혀 있는 풀이는 내가 이 문제를 보자마자 생각해낸 풀이인 이분 탐색 + 스털링 근사가 될 것이다. 숏코딩을 보니 기상천외한 naive 풀이도 있더라. 발상을 어떻게 했는지 궁금하다.

 

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

---

문제

양의 정수 n이 주어졌을 때 n의 팩토리얼인 n!을 구하는 것은 쉽다. 이번에는 n!이 주어졌을 때 n을 구해 보자.

 

입력

어떤 자연수 n에 대해 n!이 입력으로 주어진다. n!의 자리수는 \(10^6\) 이하이다.

 

예제 입력)

#예제 입력 1
120

#예제 입력 2
51090942171709440000

#예제 입력 3
10888869450418352160768000000

 

출력

n을 출력한다.

 

예제 출력)

#예제 출력 1
5

#예제 출력 2
21

#예제 출력 3
27

 

---

내 코드

from math import log, pi
def logfact(x):
    return x*(log(x)-1) + log(2*pi*x)/2 + 1/(12*x)
nfact = int(input())
data = {1:1, 2:2, 6:3, 24:4, 120:5, 720:6, 5040:7, 40320:8, 362880:9, 3628800:10, 39916800:11, 479001600:12, 6227020800:13, 87178291200:14, 1307674368000:15, 20922789888000:16, 355687428096000:17, 6402373705728000:18, 121645100408832000:19}
if nfact in data.keys(): print(data[nfact]); quit()
start,end,mid = 20,10**6,500000
error = float(1e-3)
x = log(nfact)
while True:
    mid = (start+end) // 2
    if logfact(mid) > x + error: end = mid
    elif logfact(mid) < x - error: start = mid
    else: print(mid); quit()

 

우선 n이 1 이상 20 이하인 자연수일 경우인 적당히 작은 값에 대해서는 미리 빼내 주고 시작하자. n이 충분히 작으면 스털링 근사를 활용하기가 굉장히 불편하다. 이제 조화수 근사 포스트에서 지나가듯이 언급했던 스털링 근사를 이용하자.

\(\frac{1}{n}\)항까지만 고려할 것인데, 그 이유는 n이 21 이상인 경우 \(\frac{1}{n^3}\)항부터는 0.001 이하로 매우 작아지기 때문이다. 21 이상의 n에 대해서는 인접한 두 팩토리얼의 로그값 차가 \(\log(n+1)!-\log n!=\log(n+1)>\log21>3\)이기 때문에 0.001 정도는 오차로 감안해도 되므로, 실제로 풀이 상에는 아무런 문제가 없다.

\(\frac{1}{n}\)항까지 고려한 스털링 근사는 다음과 같다.

\[\log(n!)\approx n(\log n-1)+\frac{1}{2}\log(2\pi n)+\frac{1}{12n}\]

이것이 코드 내부의 logfact 함수이다.

 

이제 준비는 모두 끝났다. 입력받은 nfact가 data의 key에 있다면 이는 1 이상 20 이하 자연수 n에 대해서 n!이라는 소리므로, 그 케이스는 빼내 주고, log(nfact)=x에 대해서 이분탐색을 진행해 준다. x=n!라고 가정하자.

\(10^6\)는 5,565,709자리의 자연수이므로, 오른쪽 끝을 넉넉하게 \(10^6\)으로 잡더라도 무방하다. 이제 이들에 대해서 이분 탐색을 사용하면 된다.

정확하게는, 왼쪽 점 start와 오른쪽 점 end에 대해서, start와 end의 중간점을 mid로 잡는다. 이 경우에는 답이 정수로 한정되어야만 하므로 (start+end)//2를 mid로 두어야 한다.

 

0.001 이하의 오차는 무시를 하여도 충분하므로 오차 error를 0.001로 두고, 다음 세 가지 케이스를 상정한 다음 각각의 케이스에 대해서 상정해주면 된다.

1. logfact(mid)가 x보다 error 이상 클 경우. 이 경우에는 mid＞n이 성립하기 때문에, n은 start와 mid 사이에 있다. 그러면 오른쪽 점인 end를 mid로 바꾸어 준 다음 다시 탐색한다.

2. logfact(mid)가 x보다 error 이상 작을 경우. 이 경우에는 mid＜n이 성립하기 때문에, n은 mid와 end 사이에 있다. 그러면 왼쪽 점인 start를 mid로 바꾸어 준 다음 다시 탐색한다.

3. 그 외의 경우. 이는 logfact(mid)가 x와 기껏해야 error만큼의 차이밖에 나지 않는다는 뜻이다. 곧, 오차 범위 내에 들어오는 것이고, mid=n으로 상정해도 된다는 것. 따라서 mid를 출력하고 프로그램을 종료하면 된다.

 

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

그럼, 오늘도 당신의 코딩 실력이 상승하기를.