[백준] 2004번: 조합 0의 개수

링크: www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

조합 0의 개수

문제

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 nCm의 끝자리 0의 개수를 출력한다.

---

문제접근

이번 문제는 수학문제이면서 약간의 논리가 필요한거 같다. 우선 조합 nCr의 일반식을 입력해보면

nCr = n!/((n-r)! * r!)이다.

처음에 나는 위 공식을 이용해서 값을 구한다음 뒤에서 부터 0의 개수를 세는 방식으로 문제를 접근했다.

그러나 역시 다른 뜻이 있었다는 걸 보여주듯이 시간 초과가 나타났다.

 

import sys

def facto(n):
    if n == 0 or n == 1:
        return 1
    else:
        result = 1
        for i in range(1,n+1):
            result *= i
        return result

def comb(n, m):
    return int(facto(n)/(facto(n-m) * facto(m)))

def calc(n, m):
    data = comb(n,m)
    data = reversed(str(data))
    count = 0
    for i in data:
        if(i == '0'):
            count += 1
        else:
            break;
    return count

def main():
    n, m = sys.stdin.readline().split()
    n = int(n); m = int(m)
    print(calc(n,m))

if __name__ == "__main__":
    main()

 

숫자가 20억까지면 int형의 거의 끝 숫자까지 사용한다는 것인데, 당연히 시간초과가 날 것을 간과했다... ㅍ_ㅍ;;;

 

따라서 단순히 공식으로 풀어내는 것이 아니라 다른 방법을 통해 문제를 푸는 것인데, 자연수에서 "1000"은 10이 3번 곱해진 것이다. 또 "4300"은 43에 10이 2번 곱해진 것이다. 따라서 입력으로 주어진 수(nCm)의 10의 개수를 세면 뒤에 존재하는 0의 개수를 얻을 수 있다.

 

그러나 nCm은 수가 커지면 시간초과가 나온다. 따라서 nCm의 공식에서 분자와 분모를 나누어서 10의개수를 세고 분자의 10의 개수에서 분모의 10개수를 빼면(뺀다고 표현했지만 사실 약분을 하는 것이다.) nCm의 10의 개수를 얻을 수 있다.

 

여기서 10은 2와 5로 나뉜다. 따라서 입력으로 주어진 수의 분자와 분모 2와 5의 개수를 세어서 빼준 후(약분), 2와 5 개수의 최소값을 통해 0의 개수를 얻을 수 있다는 결론이 나온다.

---

코드

"""
백준 알고리즘 2004번: 조합 0의 개수
https://www.acmicpc.net/problem/2004

nCr = n!/((n-r)! * r!)
아 시간초과...
0의 개수는 10이 생겨날때마다 늘어난다.
10 = 2 * 5로만들어짐 따라서
분자 n의 5의 개수에서 m, n-m의 5의 개수를 빼고(약분 하는 거임)
분자 n의 2의 개수에서 m, n-m의 2의 개수를 뺀다(약분)
2는 100개 있는데 5가 1개있으면 10은 1개 만들어 지므로
둘중에 제일 작은 수를 구하면 그게 답 
"""
import sys

def count2(n):
    count = 0
    while n != 0:
        n = n//2
        count += n
    return count

def count5(n):
    count = 0
    while n != 0:
        n = n//5
        count += n
    return count

def calc(n, m):
    cnt2 = count2(n) - (count2(m) + count2(n - m))
    cnt5 = count5(n) - (count5(m) + count5(n-m))
    return min(cnt2, cnt5)

def main():
    n, m = sys.stdin.readline().split()
    n = int(n); m = int(m)
    print(calc(n,m))

if __name__ == "__main__":
    main()