Hanbit the Developer
[C++] 백준 2004번: 조합 0의 개수 본문
https://www.acmicpc.net/problem/2004
10 = 2 * 5에서, 2와 5의 승수만을 고려하여 풀 수 있다는 아이디어를 내야한다.
nCr = n! / (r! * (n-r)!)의 각각의 팩토리얼에서 2, 5의 승수를 가져와서 연산을 해주면 된다. 예를 들어, 5C3 = 5!/(3!*2!) = (1*2*3*4*5) / ((1*2*3) * (1*2))에서 5!, 3!, 2!에는 각각 2^1, 5^1 / 2^1 / 2^1가 포함되며 2^(-1), 5^0이므로 0의 개수가 0이다. 만약 어떤 조합에서 2^3, 5^2가 나왔다면 그것의 0의 개수는 2개일 것이다.
이것을 일반화하여 n!에서 p의 승수를 구하는 함수를 작성하면 다음과 같은 코드가 나온다.
// n!에서 p의 승수를 구한다
int get_power(int n, int p) {
int res = 0;
while (n >= p) {
res += n / p;
n /= p;
}
return res;
}
특정 조합으로부터 p의 승수를 구할 수도 있다.
int get_power_from_combination(int n, int m, int p) {
return get_power(n, p) - get_power(m, p) - get_power(n - m, p);
}
마지막으로 위 함수를 2, 5에 대해서 써주면 바로 이 문제를 풀 수 있다.
전체 코드는 아래와 같다.
#include <iostream>
using namespace std;
// n!에서 p의 승수를 구한다
int get_power(int n, int p) {
int res = 0;
while (n >= p) {
res += n / p;
n /= p;
}
return res;
}
int get_power_from_combination(int n, int m, int p) {
return get_power(n, p) - get_power(m, p) - get_power(n - m, p);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
cout << min(get_power_from_combination(n, m, 2), get_power_from_combination(n, m, 5));
return 0;
}
'Algorithm > 백준' 카테고리의 다른 글
[C++] 16566번: 카드 게임 (0) | 2021.11.17 |
---|---|
[C++] 백준 11401번: 이항 계수 3 (0) | 2021.11.12 |
[C] 백준 17298번: 오큰수 (0) | 2021.11.05 |
[C] 백준 15651번: N과 M (3) - Linked List (0) | 2021.10.29 |
[C] 백준 2750번: 수 정렬하기(퀵 정렬) (0) | 2021.10.20 |