https://www.acmicpc.net/problem/2004
- 문제
두 수가 주어지면 nCm에서 끝자리 0의 개수를 구하는 문제다.
- 해설
nCm은
n! / (n-m)! * m!이다.
여기서 끝자리 0의 개수를 구하기 위해서는
1. n!에서 2*5의 개수를 구해서
2. (n-m)!에서 2*5의 개수를 빼고
3. m!에서 2*5의 개수를 빼면 된다.
1. n!에서 2와 5의 개수를 구해보자.
예를 들어 n이 25이라고 하면
25 / 2 = 12 (2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24)
2 * 2 = 4
25 / 4 = 6 (4, 8, 12, 16, 20, 24)
4 * 2 = 8
25 / 8 = 3 (8, 16, 24)
8 * 2 = 16
25 / 16 = 1 (16)
이라고 해서 25!에서 2의 개수는 12 + 6 + 4 + 1해서 23개가 된다.
이제 5의 개수를 똑같이 구해보면
25 / 5 = 5
25 / 5 = 1
이라고 해서 25!에서 5의 개수는 6개가 되어서
25!에서 끝자리 0의 개수는 6개가 된다.
2. 이제 m을 12라고 하면 (n - m)! 은 13!이 된다.
위의 1.에서 처럼 2의 개수와 5의 개수를 구하면
10개와 2개가 되어서
2 * 5는 2개가 된다.
3. 이제 m이 12니깐 12!에서 2와 5의 개수를 구하면
똑같이 10개와 2개가 되어서
2 * 5는 2개가 된다.
4. 마지막 6 - 2 - 2 = 2이므로 정답은 2가 된다.
- 풀이
#include <iostream>
#include <algorithm>
using namespace std;
long long twos(int n)
{
long long cnt = 0;
for (long i = 2; i <= n; i *= 2)
{
cnt += n / i;
}
return cnt;
}
long long fives(int n)
{
long long cnt = 0;
for (long i = 5; i <= n; i *= 5)
{
cnt += n / i;
}
return cnt;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
long long answer;
cin >> n >> m;
answer = min(twos(n) - twos(m) - twos(n - m), fives(n) - fives(m) - fives(n - m));
cout << answer;
return 0;
}
- 새롭게 알게 된 점
'Algorithm > Baekjoon BOJ' 카테고리의 다른 글
[백준][C++] 15649 : N과 M (1) (0) | 2022.10.21 |
---|---|
[백준][C++] 11051: 이항 계수 2 (0) | 2022.10.21 |
[백준][C++] 3036 : 링 (0) | 2022.10.21 |
[백준][C++] 2981: 검문 (0) | 2022.10.21 |
[백준][C++] 1934 : 최소공배수 (0) | 2022.10.21 |