166. 조합 0의 개수
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
- 설명 참고 :
https://www.acmicpc.net/board/view/60835,
https://tmdrl5779.tistory.com/95
https://www.acmicpc.net/board/view/72777
그냥 팩토리얼이었다면- 소인수분해해서 2와 5의 갯수만 세어주는 것, 5가 몇개 들어있는지 세주면 되는 것
- 5*5 곱하면 앞에 2 최소 두번은 있음 (2,4,8 등등..)
- 따라서 5만 세주면 되는 것이지
조합의 경우는 뭐가 더 적을지 몰라
그래서 마지막에 비교해주는 시간을 가지는 것이지
(+)
예를 들어 10!에 곱해진 2의 개수를 구할거에요.
10!에서 2가 곱해져 있는 수들은 2,4,6,8,10이 있습니다.
2가 1번 곱해져 있는 수는 2,6,10
2가 2번 곱해져 있는 수는 4
2가 3번 곱해져 있는 수는 8이므로,
2의 개수로 표현하면, 2,6,10은 1 , 4는 2 , 8은 3
10//2를 하면 2,4,6,8,10이 더해지고
10//4를 하면 4,8이 더해지고
10//8을 하면 8이 더해집니다.
n, m = map(int, input().split())
def count(k, n) :
res = 0
while n != 0:
n = n // k
res += n
return res
print(min(count(5,n) - count(5,n - m) - count(5, m), count(2,n) - count(2,n - m) - count(2, m)))
//이 부분은 조합이라서 (n!/(n-m)!m! )
< 내 틀렸던 풀이, 문제점>
https://www.acmicpc.net/board/search/all/problem/2004
20억의 팩토리얼을 계산하는 것 자체가 시간 제한상 절대 감당할 수 있는 수준이 아닙니다. 팩토리얼을 계산하지 않고 문제를 풀어야 합니다.
from math import comb
import sys
n,m=map(int,sys.stdin.readline().split())
initi=1
dividi=1
for i in range(m) :
initi*=n
n-=1
for j in range(m,0,-1) :
dividi*=j
res=list(str(initi//dividi))
# print(res)
# print(comb(9,3))
cnt=0
for i in range(len(res)-1,-1,-1):
if res[i]!='0':
break
else :
cnt+=1
print(cnt)
- 시간초과
- 방법을 다르게 해야 함
