팩토리얼 끝에서 가장 먼저 나오는 0이 아닌 수를 찾는 방법

1. 문제1

 

2553번: 마지막 팩토리얼 수 (acmicpc.net)

2553번: 마지막 팩토리얼 수

 

2. 풀이

 

저번에 풀었던 문제와는 다르게 팩토리얼 계산한 값에서 마지막에서 0이 아닌 처음으로 다른 수가 나올때, 그 수를 출력하는 문제

 

쉽게 생각할 수 있는 방법은..?

 

저번에 배운 마지막에 0이 나오는 개수를 구하는 방법을 응용하기

 

마지막에 나오는 0의 개수 k를 구하고, n!을 계산하여 prod라고 저장한 다음에...

 

prod를 $10^{k}$로 나눠준다면? 일의 자리가 정답이 된다

 

일의 자리는 어떻게 구해? str()로 바꿔서 -1번을 뽑아?

 

아니 str()로 바꾸는게 생각보다 시간 많이 먹어

 

10으로 나눈 나머지가 일의자리잖아 그러니까 10으로 나눈 나머지를 출력

 

from sys import stdin

def factorial_zero(n):
    
    answer = 0

    i = 1

    while 1:
        
        x = n//(5**i)

        if x == 0:
            
            break

        answer += x

        i += 1

    return answer     

n = int(stdin.readline())

prod = 1

for i in range(1,n+1):
    
    prod *= i

prod //= 10**(factorial_zero(n))

print(prod % 10)

 

 

3. 최적화하기

 

이렇게 풀어도 답이긴 한데 다른 방법이 있다

 

일단 n!을 계산하는건 맞는데

 

n!을 계산하는 와중에 자리수를 전부 가져가는게 아니라, 뒤에서 x자리만큼만 가져가고 싶은거임

 

그러기 위해 n!을 for문으로 계산하면서, 계산한 결과를 $10^{x}$로 나눈 나머지를 저장하는것

 

왜 이래도 되는 것이냐?

 

정수론에서 정수를 전부 곱하고 mod연산을 하는 것과, 곱하면서 mod연산을 하는 것은 동일하다는 것을 배웠다

 

후자가 곱하면서 수가 줄어드니까 시간복잡도가 줄어든다는 것도 배웠고

 

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? - (tistory.com)

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

 

 

여기서 핵심은 정수를 곱하면서 $10^{x}$로 나눈 나머지를 저장해 맨 뒤 x자리만 저장해둔다면,

 

곱하면서 반드시 맨 뒤 x자리만 정확히 알 수 있다.

 

그런데 이 문제는 마지막에 0이 나오는 것을 제거하고 첫번째로 0이 아닌 수가 나올때, 그것을 출력하는 것이다

 

n!을 prod에 차례대로 곱하면서 계산하는데..

 

prod가 10으로 나누어 떨어진다면, 1의 자리가 0이라는 뜻이다.

 

그래서 prod를 10으로 나눈 몫으로 갱신하여 1의 자리가 0인 경우를 제거하는 것이다.

 

그리고 수가 너무 커지는 것을 방지하기 위해 $10^{7}$로 나눈 나머지를 저장해 맨 뒤 7자리만 알아가도록 한다

 

이유는 $5^{6} =  15625$이고 n = 20000이 최대이므로, prod에 $5^{6}$을 곱하는 순간, $10^{6}$이 곱해지는거라, 뒤에 0이 6개 붙는다.

 

따라서 최소한 뒤에서 7자리는 확보해가고 있어야한다.

 

반복문을 탈출하고 나온 prod는 n!에서 마지막 0인 수를 모두 지우고, 처음으로 0이 아닌 수부터 총 6자리를 출력해준다.

 

이제 원하는건 0이 아닌 처음으로 나온 수이므로, prod를 10으로 나눈 나머지를 출력

 

from sys import stdin

n = int(stdin.readline())

prod = 1

for i in range(1,n+1):
    
    prod *= i

    ##마지막이 0을 제거
    while prod % 10 == 0:
        
        prod //= 10
    
    #너무 수가 커지면 느려지므로 7자리만 확보하기 위함
    #5**6 = 15625 이기 때문에, 최대 n = 20000에 가장 가까우므로
    #최소한 뒤에서 7자리는 확보해가고 있어야함
    prod %= (10**7)

print(prod % 10)

 

4. 문제2

 

1564번: 팩토리얼5 (acmicpc.net)

1564번: 팩토리얼5

 

 

5. 풀이

 

뒤에서부터 0인 개수 factorial_zero를 하고,

 

n!을 계산한 다음, factorial_zero로 나눠서 마지막부터 5자리를 출력해준다.

 

근데 이 문제는 이 방법은 통하지 않는다

 

n의 최대범위가 10의 6제곱이라 prod를 계산하는데만 해도 상당히 오래걸리므로, 압축 테크닉이 필요

 

정수를 mod로 나눈 나머지를 변수에 저장시켜서 자리수를 줄이자

 

i를 곱해나가면서, prod가 10으로 나누어 떨어진다면, 나누어 떨어지지 않을때까지 prod//=10으로 몫을 갱신하면..

 

뒤에서부터 0인 자리는 모두 제거될것

 

그리고 prod를 $10^{13}$으로 나눈 나머지를 저장해두어, 뒤에서부터 13자리만 계산에 이용하도록 한다.

 

너무 커지면 시간안에 반복문도 못도니까

 

--------------------------------------------------------------------------------------------

 

여기서 왜 13자리를 뽑아야할까?

 

n!에서 맨 뒤에 오는 0의 개수는 5의 지수로 표현되는데, $5^{8} = 390625$ 

 

$5^{9} = 1953125$으로 N의 최대 범위를 넘어가니, prod에 $5^{8}$을 곱하면, 뒤에 0이 8개 붙는다.

 

따라서 최대한 뒤에서 8+5 = 13자리는 알고 있어야한다.

 

------------------------------------------------------------------------------------

 

아무튼 반복문을 탈출하면 $10^{5}$로 나눈 나머지를 저장하면 뒤에서부터 5자리 확보 가능

 

물론 그런데.. 예를 들어 

 

반복문 돌고 prod가 3360000000000000이라서, 뒤에서부터 0이 모두 제거되어 336만 나온다면?

 

어쨌든 5자리를 출력하라 했으니 앞에 '0'을 붙여서 5자리로 되게 만들어준다.

 

이때, 반복문을 돌아서 앞에 '0'을 붙여 5자리를 만들수 있지만

 

파이썬의 특징을 이용해 문자열 곱연산을 이용해  '0'*(5-len(str(x)))+str(x) 한줄로 간단하게 표현 가능!

 

from sys import stdin

n = int(stdin.readline())

prod = 1

for i in range(1,n+1):
    
    prod *= i
    
    while prod % 10 == 0:
        
        prod //= 10
    
    prod %= 10**13

x = (prod % (10**5))

print('0'*(5-len(str(x)))+str(x))