백준 1564 팩토리얼5 python

0을 뺀 끝 5자리만 구하면 된다고 해서 매 계산마다 5자리만 딱 남게 계산했는데
제출결과 오답이었다.
그리고 실제 반례를 찾다가 당연한거였지만 생각치 못한 부분이있었다.

📜 문제 바로 가기 : 팩토리얼5

제출코드

파이썬

import sys
input = sys.stdin.readline

N = int(input())

def CUT(v, idx):
    s = str(v)
    for i in range(len(s)-1, -1, -1):
        if s[i] != "0":
            break
    
    return int(s[max(i-idx, 0) : i+1])
    
v = 1
for i in range(1, N+1):
    v = CUT(v*i, 11)

v = CUT(v, 4)
ans = "0" * (5 - len(str(v))) + str(v)
print(ans)

접근방법

871782912 * 15 와 82912 * 15를 비교해보자.
계산기 쓰지말고 그냥 보면 맨 뒤 5자리가 82912로 같기 때문에 계산결과도 뒤 5자리는 같겠지 생각했는데 실제 계산 결과는 달랐다.

이번엔 숫자를 줄여서 125 * 9 와 25 * 9는 앞 숫자의 뒤 2자리가 같으니 계산 결과의 맨 뒤 2자리가 같을까? 아니다.

십진수 계산에서 한 경우는 계산이 끝나 바로 오는경우고 한 경우는 내 앞자리에 계산할게 또 있어서 그거 계산값이랑 더해서 내려오는 경우다. 말로 설명하기가 어려운데...
직접 손으로 저 계산을 해보면 무슨 말인지 바로 알 것이다!

결론은 5자리 까지 구하면 최소 6자리까지는 그 결과를 지켜봐야 한다는 것이다.

그런데 이문제는 뒤에 붙은 0은 모두 제거하기 때문에 0 이 최대로 나오는 경우를 제외하고
근데 답은 12자리까지 여유를 줘야되는데 사실 이부분은 힌트를 봤다.
아마 N! 과정에서 0이 꽤 많이 붙은 경우가 있는 거 같다!