-
1564. [Python]팩토리얼5Python_알고리즘/Silver II 2023. 8. 13. 15:09
1. 문제
https://www.acmicpc.net/problem/1564
1564번: 팩토리얼5
첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 수학
3. 파이썬 코드
N = int(input()) ans = 1 # 1 ~ N 값까지 반복문을 통해서 곱해나감 for i in range(1,N+1): # ans 값의 곱에 10^13 의 나머지를 계산해준다. # N값이 1,000,000 까지 들어오기 때문에 10^6 * 10^6 + 1의 값까지 10의 배수의 나머지를 취해준다. ans = (ans*i) % (10**13) # 만약 곱한 ans 가 10으로 나눠질 경우 if ans % 10 == 0: # ans 의 10의 몫을 계속 구한다. while ans % 10 == 0: ans //= 10 # 출력을 위해 문자열로 변경 ans = str(ans) # 끝에서 5자리 출력 ans_length = len(ans) print(ans[ans_length-5:])
4. 문제를 풀고난 후 생각
- 문제를 읽고 답을 구하는 것은 어렵진 않았다.
- 답을 내기 위해서 시간초과를 내지 않고 나머지로 나눠주는 경우를 생각하는 것이 오래걸렸다.
- 맨 끝자리 값이 10이 되기 위해서는 5의 갯수가 중요하다. 1,000,000보다 작은 5의 제곱 수 중 390,625 가 존재하며 이는 5^8 이다.
- 위 값이 곱해졌을 경우 한번에 최대 8자리가 줄어들기 때문에 나머지 값을 8+5(5자리까지 구해라)+1 해서 13자리 까지 나머지의 값을 저장하록 했다.
- 계산을 하며 나머지를 얼마를 나눠야 하는지 고민을 많이 했고 질문 게시판 등을 찾아가며 스스로 생각했던 점을 정리하였다.
5. 문제를 푸는데 도움이 되는 지식
- 수학
'Python_알고리즘 > Silver II' 카테고리의 다른 글
5002. [Python]도어맨 (1) 2023.08.27 1012. [Python]유기농 배추 (0) 2023.08.19 5397. [Python]키로거 (0) 2023.08.11 1260. [Python]DFS와 BFS (0) 2023.08.08 1874. [Python]스택 수열 (0) 2023.08.07