역팩토리얼

• 1부터 i까지 곱해서 i!를 계산해 나가다가 주어진 수와 같아지면 종료..하는 것은 O(n)이긴 하지만, 수가 너무 커지기 떄문에 불가능한 방법이다.
• 이 아이디어를 살려서 O(n)으로 푸는 방법은, 로그를 취한 값을 더해 나가는 것이다. 입력받는 수는 너무 커서 정수로 변환할수도 없지만, 문자열로 입력받았을때 문자열의 길이 l이 수의 자리수이고, 따라서 l-1 ⇐ log10(n!) < l 이 된다. 이제 log10(i!) = log10(1) + log10(2) + … + log10(i)가 저 범위 안에 들어올때까지 i를 늘려가면서 계산해주면 된다.
  • n이 작을 경우에는 범위가 정밀하지 않아서 오차가 생길수 있다. 작은 n에 대해서 테이블을 만들어 따로 계산할 수도 있고, 입력 받은 숫자에서 첫번째 숫자 x를 추가로 계산에 포함해서 (l-1)*log10(x) ⇐ log10(n!) < l*log10(x) 로 범위를 좁혀도 해결 가능하다.
• log10(i!)를 log10(1) + log10(2) + … + log10(i) 과 같은 식으로 구하는 대신에, 스털링 근사를 이용해서 바로 계산하는 방법도 있다. ko:스털링 근사에 따르면 $\ln n!\sim n(\ln n-1)+{\frac 12}\ln(2\pi n)$ 이 성립한다. 입력받은 수에 대한 로그값을 자연로그로 바꿔 구하고, 이 값과 비교해서 찾으면 된다. 이제 ln(i!)을 O(1)에 계산이 가능하기 때문에, 이분탐색을 사용하면 O(logn)으로 더 빠르게 찾을 수 있다.
• 계산시간이 오래 걸리는 문제가 아니다보니, 내 경우는 O(n)코드가 더 빨리 동작했다.

"""Solution code for "BOJ 13294. 역팩토리얼".

- Problem link: https://www.acmicpc.net/problem/13294
- Solution link: http://www.teferi.net/ps/problems/boj/13294
"""

import itertools
import math


def main():
    n_fac = input()
    log_n_fac = len(n_fac) - 1 + math.log10(int(n_fac[0]))

    s = 0
    for i in itertools.count(1):
        s += math.log10(i)
        if s >= log_n_fac:
            answer = i
            break

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 13294. 역팩토리얼".

- Problem link: https://www.acmicpc.net/problem/13294
- Solution link: http://www.teferi.net/ps/problems/boj/13294
"""

import math
from teflib import algorithm


def log_fac(x):
    return (math.log(math.factorial(x)) if x < 10 else
            (x * (math.log(x) - 1) + math.log(2 * math.pi * x) / 2))


def main():
    n_fac = input()
    log_n_fac = math.log(10) * (len(n_fac) - 1) + math.log(int(n_fac[0]))

    hi = len(n_fac) + 10
    answer = algorithm.binary_search(1, hi, lambda x: log_fac(x) >= log_n_fac)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.binary_search