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, 조합론)

- https://somjang.tistory.com/entry/BaeKJoon-2004번-조합-0의-개수-Python

[BaeKJoon] 2004번: 조합 0의 개수 (Python)