[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 7894번 _ 큰 수

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

7894번: 큰 수

[문제]

많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다.

수가 주어지면, 그 수의 팩토리얼의 자리수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 테스트 케이스의 수가 주어진다. 다음 줄부터 한 줄에 하나씩 정수 m이 주어진다. (1 ≤ m ≤ 107)

[출력]

입력으로 주어지는 수 m마다 m!의 길이를 출력한다.

 

[아이디어]

1) 수와 자리수를 동시에 업데이트 해나가며, 자리 수를 배열에 보관하게 했다.

2) 다루는 연산이 커지지 않게 수를 계속 10 미만으로 관리해준다.

 

# Pypy3로 제출
a=[1]*(10**7+1)
x=1
for i in range(1,10**7+1):
    x*=i
    tmp=a[i-1]
    while x>10:
        x/=10
        tmp+=1
    a[i]=tmp
t=int(input())
for _ in range(t):
    print(a[int(input())])

Python3로 제출하면 메모리 초과가 났다.