https://www.acmicpc.net/problem/13294
문제요약
- n!이 주어졌을때 n을 구하자
- 자리수가 10^6
접근법
- 직접 모두 곱해보기에는 숫자도 크고 계산도 안됨 => 효율적으로 곱한다
- 0이 나타난다 => 2와 5와 곱해졌다 => 5가 몇번 나타났다? 를 알 수 있음
- 0의 개수 => 어디쯤의 5까지 갔는지 알 수 있음
- 5 10 15 20 25 ..여기쯤.. 30
- 전체 자리수가 아니라 일부 자리수만 곱하기로 유지
- 1, 2, 3, 4, .... 곱해나간다
- 0이 나온다? => 0을 제거
- 다른 숫자가 나온다? => 일정 부분 자리수를 유지(예를들어 4자리만 유지)
- 제거된 0의 개수와 입력으로 주어진 0의 개수가 같을때 곱해진 값을 비교
- 설명이 잘 안되는데
- 1부터 다 곱해본다
- 0이 나오면 제거한다 + 원래 입력에서 0이 몇개인지 비교해가면서 제거한다
- 곱하기의 결과를 모두 저장하지 않고 일부 자리수만 저장한다
- 0으로 판단 + 일부 자리수로 판단
newbieski