Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 서브쿼리
- DP
- 다이나믹프로그래밍
- BFS
- 분할정복
- 다이나믹 프로그래밍
- 크루스칼
- 해시
- 트리
- DFS
- 수학
- 브루트포스
- 투포인터
- 시뮬레이션
- 플로이드-워셜
- 그래프 이론
- 재귀
- 그래프 탐색
- 구현
- 다시
- 백트래킹
- join
- 다익스트라
- 에라토스테네스의 체
- MST
- 자료구조
- 누적합
- 우선순위큐
- 그리디
- GROUP BY
Archives
- Today
- Total
기록하고 까먹지 말기
2004 본문
날짜 : 2022. .
사용 언어 : python
문제

코드
import sys
def cntnum(n, c):
cnt = 0
while n > 0:
cnt += n // c
n = n //c
return cnt
n, m = map(int, sys.stdin.readline().split())
result = min(cntnum(n, 2) - (cntnum(m, 2) + cntnum(n-m, 2))
, cntnum(n, 5) - (cntnum(m, 5) + cntnum(n-m, 5)))
print(result)
알게된 점
- 맨 처음 조합을 구하고 문제를 풀었는데 시간초과가 발생했다.
- 알고보니 팩토리얼의 소인수 2, 5의 지수를 구하는 문제였다.
- 그래서 2, 5의 소인수의 개수를 구하고 그 중 작은 수를 출력하는 방식으로 문제를 해결했다.
(10은 2와 5를 공통으로 소인수로 갖기 때문)
참고 사이트
- https://velog.io/@ledcost/백준-2004-파이썬-조합-0의-개수-실버2-조합론
[백준 2004 파이썬] 조합 0의 개수 (실버2, 조합론)
1676 팩토리얼 0의 개수와 비슷하지만, 0의 개수를 구하려는 값이 팩토리얼 형태가 아님. 1676번 문제의 원리는 그대로 써먹을 수 있다.
velog.io
- https://somjang.tistory.com/entry/BaeKJoon-2004번-조합-0의-개수-Python
[BaeKJoon] 2004번: 조합 0의 개수 (Python)
1일 최소 1문제 4일차! 오늘의 문제는 조합 속의 0의 개수를 구하는 문제입니다. 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net 먼저 nCk일 경우 왼쪽..
somjang.tistory.com
'전공 > 백준' 카테고리의 다른 글
BFS 응용문제(이코테) (0) | 2022.10.08 |
---|---|
DFS 응용문제(이코테) (0) | 2022.10.08 |
1676 (0) | 2022.10.06 |
14916 (0) | 2022.10.06 |
에라토스테네스의 체 구현 (0) | 2022.10.05 |