백준(baekjoon) 2004번: 조합 0의 개수(실버 2, 파이썬 PYTHON) - 정수론 및 조합론

문제

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

 

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

import sys

n,m=map(int,sys.stdin.readline().split())

def count_two(num):  
  save=2
  count=0
  while(save<=num):
    count+=num//save
    save*=2
  return count

def count_five(num):  
  save=5
  count=0
  while(save<=num):
    count+=num//save
    save*=5
  return count

two=count_two(n)-count_two(m)-count_two(n-m)  
five=count_five(n)-count_five(m)-count_five(n-m)  
print(min(two,five))

 

※ 정수론 및 조합론

 

 

이 문제는 팩토리얼 계산을 직접 진행하면 시간 초과가 난다.

 

● 끝자리의 0의 개수는 2와 5의 곱으로 이루어진다. 따라서 총 결과 값에 2가 곱해져 있는 횟수와 5가 곱해져 있는 횟수를 구하는 것이 이 문제의 핵심이다!

 

● 우선 매개변수로 들어온 값의 팩토리얼 값에 2와 5가 곱해져 있는 횟수를 구하는 함수 count_two(), count_five() 를 각각 정의해준다.

 

예 ) count_two(9) 의 진행과정

-> 8! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

-> 9, 8, 7, 6, 5, 4, 3, 2, 1 에서 2의 배수의 개수 9//2 의 값을 count 에 더해준다.

-> 9, 8, 7, 6, 5, 4, 3, 2, 1 에서 2 * 2의 배수의 개수 9//4 의 값을 count 에 더해준다.

-> 9, 8, 7, 6, 5, 4, 3, 2, 1 에서 2 * 2 * 2의 배수의 개수 9//8 의 값을 count 에 더해준다.

-> 2 * 2 * 2 * 2 는 9보다 크므로 루프를 탈출한다.

이러면 9! 에 곱해져있는 2의 수를 모두 구할 수 있다!!

 

예) count_five(27) 의 진행과정

-> 27! = 27 * 26 * .... * 2 * 1

-> 27, 26 ... ,2, 1 에서 5의 배수의 개수 27//5 의 값을 count 에 더해준다.

-> 27, 26, ... ,2, 1 에서 5 * 5 의 배수의 개수 27//25 의 값을 count 에 더해준다.

-> 5 * 5 * 5 는 27보다 크므로 루프를 탈출한다.

이러면 27! 에 곱해져있는 5의 수를 모두 구할 수 있다!!

 

● (n m) = n! / m! * (n-m)! 이므로 최종 결과 값에 곱해져 있는 2의 수는 count_two(n) - count_two(m) - count_two(n-m), 최종 결과 값에 곱해져 있는 5의 수는 count_five(n) - count_five(m) - count_five(n-m) 이다.

 

● 총 결과값의 끝에 있는 0의 개수는 2와 5의 쌍이 얼마나 있느냐에 따라 달라지므로 결국 위에 구한 2의 수와 5의 수 중 더 작은 값이 0의 개수이다.

 

 

결과