-
3474. [Python]교수가 된 현우Python_알고리즘/Silver III 2023. 7. 31. 19:28
1. 문제
https://www.acmicpc.net/problem/3474
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 정수론
3. 파이썬 코드
import sys input = sys.stdin.readline T = int(input()) # Test Case 만큼 반복 for _ in range(T): # input 값으로 들어온 N이 5보다 작은경우 0의 갯수는 0 개다 N = int(input()) if N < 5: print(0) else: # 5라는 변수를 받고 cnt 값에 N을 5로 나눈 몫을 더해준다 five_num = 5 cnt = N//five_num # N보다 작은 5의 제곱 수를 가지고 cnt 값을 측정한다. while five_num <= N: # 이미 5로 구했기 떄문에 5를 곱해준다 five_num *= 5 # N이 만약 25보다 작으면 몫에 0이 들어가기 떄문에 cnt 값은 변화가 없다. cnt += (N//five_num) print(cnt)
4. 문제를 풀고난 후 생각
- 제일 오른쪽에 0이 오기 위해서는 2와 5의 곱이 필요하다.
- 2의 갯수를 세는 것은 무의미하며 이유는 2가 아무리 많더라도 결국 5의 갯수가 적으면 최대 5의 갯수만큼 0 이 만들어지기 떄문이다.
- N 값이 10억까지 오기 떄문에 반복문으로 해결할 수 없다는 것을 인지해야 하고 0이 되는 조건을 생각할 수 있어야 해결할 수 있다.
- 이러한 이유로 불필요한 연산 없이 N 값보다 작은 5의 제곱수들의 갯수를 더하면 오른쪽 0의 갯수가 되는 것을 생각할 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- 정수론
'Python_알고리즘 > Silver III' 카테고리의 다른 글
2607. [Python]비슷한 단어 (0) 2023.08.02 1021. [Python]회전하는 큐 (0) 2023.08.02 3077. [Python]임진왜란 (0) 2023.07.26 3273. [Python]두 수의 합 (0) 2023.07.25 2512. [Python]예산 (0) 2023.07.18