[파이썬(Python)] 백준 2004번 : 조합 0의 개수

풀이

팩토리얼을 사용하면 재귀함수를 사용하게 되어서 시간초과 가 일어난다.

 

import sys input = sys.stdin.readline def factorial(x):     res = 1     for i in range(1, x+1):         res *= i     return res def cnt_zero(x):     cnt = 0     for i in x:         if i == '0':             cnt += 1         else:             break     return cnt n, m = map(int, input().split()) result = str(factorial(n) // (factorial(n-m) * factorial(m))) result = reversed(result) cnt = cnt_zero(result) print(cnt)

따라서 다시 생각해보았다.

재귀함수를 빼고 뒤에 0이 나오는 경우의 수를 생각해보면 5와 2가 나올때, 계산 결과의 뒤에 0이 존재할 수 있다.

import sys input = sys.stdin.readline def ans(x, y):     cnt = 0     while x:         x//=y         cnt += x     return cnt x, y = map(int, input().split()) a5 = ans(x, 5) - ans(y, 5) - ans(x-y, 5) a2 = ans(x, 2) - ans(y, 2) - ans(x-y, 2) result = min(a5, a2) print(result)

솔직히 생각하기 쉽지 않았기 때문에 구글링을 통해 아이디어를 얻어 코딩을 하게 되었다.