문제:
nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.
입력:
첫째 줄에 정수 n,m(0<=m,n<=2,000,000,000 ,n!=0)이 들어온다.
출력:
첫째 줄에 0의 개수를 출력한다.
풀이 방법:
이와 비슷한 문제로 팩토리얼에서 0의 개수를 구하는 문제와 유사하다. 조합은 팩토리얼들의 연산들로 구할 수 있기 때문이다. 그 문제와 마찬가지로 nCm를 소인수 분해 했을 때 2의 갯수와 5의 갯수가 전체 0의 갯수와 관련있게 된다. 따라서 2와 5로 매번 나누면서 count를 하나씩 증가시켰더니 시간초과가 발생해버렸다. 아무래도 2,000,000,000 와 같이 엄청 큰 수가 들어 있는 것 같다.
따라서 시간초과를 해결하기 위해서 방법을 알아보는 도중에 2의 제곱수로 나눈 몫을 계속해서 더한 것이 2의 총 갯수가 된다는 것이였다. 간략히 그 이유를 설명하면 n!에 2가 들어 있는 수들은 크게 2의 배수, 4의 배수, 8의 배수....와 같이 있다고 생각할 수 있다. 예를 들어 10!이라고 가정하면 먼저 2의 배수를 세면 2, 4, 6, 8, 10이 있고 이 들의 개수를 하나씩 카운트를 증가시킬 수 있고, 그 다음에는 4의 배수는 4, 8이고 8의 배수는 8 하나이므로 총 8개의 2가 있게 된다. 표로 보면 다음과 같다.
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
계 |
1 |
|
1 |
|
1 |
|
1 |
|
1 |
5 |
|
|
1 |
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
1 |
|
|
1 |
1 |
|
3 |
|
1 |
|
3 |
|
1 |
8 |
이와 같은 방법으로 5를 구한다음에 nCm =n! / (m! * (n-m)!) 이므로 이에 맞춰서 2의 갯수와 5의 갯수를 구한 뒤에 더 작은 값이 0의 갯수가 될 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | a,b=map(int,input().split()) def counts(N): answer2=0 answer5=0 count=1 while (True): if N//(5**count)>0: answer5+=N//(5**count) count+=1 else: break count=1 while (True): if N//(2**count)>0: answer2+=N//(2**count) count+=1 else: break return answer2,answer5 a1,b1=counts(a) a2,b2=counts(b) a3,b3=counts(a-b) print(min(a1-a2-a3,b1-b2-b3)) | cs |
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2164. 카드2 (0) | 2019.07.18 |
|---|---|
| [BOJ]4949. 균형잡힌 세상 (0) | 2019.07.17 |
| [BOJ]2217. 로프 (0) | 2019.07.15 |
| [BOJ]11047. 동전0 (0) | 2019.07.14 |
| [BOJ]1931. 회의실배정 (0) | 2019.07.13 |