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

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

2004번: 조합 0의 개수

 

 

 

 

---

- 문제

 

  두 수가 주어지면 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;
}

 

---

- 새롭게 알게 된 점