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

 

2004번: 조합 0의 개수

---

문제

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

 

입력

첫째 줄에 정수 n,m (0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

 

출력

첫째 줄에 nCm의 의 끝자리 0의 개수를 출력한다.

 

---

💻 코드 및 해설

#include <iostream>
#include <algorithm>
using namespace std;

int countDivisors(int num, int a) {
    int count = 0;
    while (num >= a) {
      count += num/a;
      num /= a;
    }
    return count;
}

int main() {
  int n, m;
  cin >> n >> m;
  int cnt2 = countDivisors(n, 2) - countDivisors(n-m, 2) - countDivisors(m, 2);
  int cnt5 = countDivisors(n, 5) - countDivisors(n-m, 5) - countDivisors(m, 5);

  cout << min(cnt2, cnt5);
}

---

countDivisors 함수

⇒ n!이 a로 몇 번 나누어지는지 구하는 함수

• 25! 즉, 25 x 24 x 23 x 22 x …. x 5 x 4 x 3 x 2 x 1이 5로 몇 번 나누어지는지 구하는 함수
  • 5가 들어있는 5의 배수, 25, 20, 15, 10, 5에서 5가 몇 번 나오는지 찾으면 됨
• num이 5보다 클 때까지 반복하면서,
  • num을 5로 나눈 몫을 count에 더하고
  • num을 5로 나눈 값을 num에 저장

 

int countDivisors(int num, int a) { // n!이 a로 몇 번 나누어지는지 구하는 함수
    int count = 0; 
    while (num >= a) { //num이 a보다 클 때까지 반복
      count += num/a; // num을 a로 나눈 몫을 count에 더하고,
      num /= a; // num을 a로 나눔 
    }
    return count;
}

---

main

int main() {
  int n, m;
  cin >> n >> m;
  int cnt2 = countDivisors(n, 2) - countDivisors(n-m, 2) - countDivisors(m, 2);
  int cnt5 = countDivisors(n, 5) - countDivisors(n-m, 5) - countDivisors(m, 5);

  cout << min(cnt2, cnt5);
}

 

• n, m을 입력받아서,
• cnt2에는 nCm 값에서 2가 몇 번 나오는지 저장
  • n!에서 2가 나오는 개수에서 (분자) (n-m)!에서 2가 나오는 개수, m!에서 2가 나오는 개수(분모)를 빼줌
• cnt5에는 nCm 값에서 5가 몇 번 나오는지 저장
  • n!에서 5가 나오는 개수에서 (분자) (n-m)!에서 5가 나오는 개수, m!에서 5가 나오는 개수(분모)를 빼줌
• cnt2, cnt5중 작은 수를 출력

---

⚠️ 잘못된 풀이 _ 시간초과

#include <iostream>
using namespace std;

int main() {
  int n, m;
  float result = 1; // int로 하니까 나누기 때문에 값이 달라져서 float로 선언
  cin >> n >> m;
  int temp;
  temp = m;
  
  for (int i = n-m+1; i < n+1; i++) {
    result *= i;
    result /= temp;
    temp--;
  }

  int num = 10;
  int count = 0;
  while (int(result) % num == 0) {
    num *= 10;
    count++;
  }
  cout << count;
}

 

 

처음에 보자마자 생각나는 대로 푼 코드 

• for문을 이용해서 nCm 조합의 값을 직접 구하고,
• 10으로 나누면서 마지막 0의 개수가 몇인지 구하는 코드

시간 초과가 나서 nCm 조합의 값을 구하는 것이 아님을 깨닫고 다른 방법을 시도했다

---

#include <iostream>
#include <algorithm>
using namespace std;

int countDivisors(int a, int b) {
    int count = 0;
    while (a % b ==0) {
      a /= b;
      count++;
    }
    return count;
}

int main() {
  int n, m;
  cin >> n >> m;
  int temp;
  temp = m;
  int cnt2 = 0;
  int cnt5 = 0;
  
  
  for (int i = n-m+1; i < n+1; i++) {
    cnt2 += countDivisors(i, 2) - countDivisors(temp, 2);
    cnt5 += countDivisors(i, 5) - countDivisors(temp, 5);

    temp--;
  }
  cout << min(cnt2, cnt5);

}

 

• 팩토리얼에서 2또는 5로 나눈 개수를 활용해야 한다는 것을 알았지만,
• 앞서 만든 for문을 활용하여 팩토리얼에서 곱해지는 숫자 안에서의 2 또는 5로 나누어진 개수를 이용해 풀었다.

ex) 10!이면 10에서 2가 나눠지는 개수, 9에서 2가 나눠지는 개수, 8에서 2가 나눠지는 개수 ... 를 더해서 구함

-> for문 안에 while문이 들어가는 형태라 반복이 너무 많이 일어나 시간초과가 일어날 수 밖에 없음 

---

📍 참고 링크

 

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

---

[팩토리얼 0의 개수]

조합 0의 개수와 팩토리얼 0의 개수 문제가 매우 유사해서 함께 풀어보면 좋을 것 같다.

1676번: 팩토리얼 0의 개수