[C++]백준 - 2004번 문제

2004번: 조합 0의 개수 (acmicpc.net)

2004번: 조합 0의 개수

 

2004번 : 조합 0의 개수

---

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

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

지난 번 1676번 문제와 꽤나 유사합니다.

10의 개수를 세는 것이니, 2와 5의 개수를 세서 10을 몇 개 만들 수 있는지 확인합니다.

 

1676번과 달리, 이번엔 2의 개수도 고려해야 합니다.

 

예를 들어, 55 C 2를 구한다면,

(55 * 54) / (2 * 1)이므로, 55 * 27에는 5는 있지만 2는 없어서 10을 만들 수 없습니다.

 

pair를 써서 5와 2의 개수를 저장하고, 더 적은 개수를 정답으로 제출하면 될 것 같습니다.

 

이제 N과 M을 받았을 때, 조합의 식을 살펴보면, N! ÷ (N-M)! ÷ M!이라는 사실을 알 수 있습니다.

1676번 문제와 동일한 방식으로 팩토리얼 별 2와 5의 개수를 구해서 나누어주도록 하겠습니다.

 

for문이 많이 들어가지만, 실제 동작 시간은 굉장히 적기 때문에 수행 시간에는 문제 없을 것입니다.

 

코드

---

#include <iostream>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    
    pair<int, int> two_five = make_pair(0,0); //2와 5의 개수
    
    //N!에서 2와 5의 개수를 구함
    for(int i = N; 0 < i; i /= 2) two_five.first += i / 2;
    for(int i = N; 0 < i; i /= 5) two_five.second += i / 5;
    
    //위에서 구한 개수에서 N-M!만큼의 2와 5의 개수를 뺌
    for(int i = N-M; 0 < i; i /= 2) two_five.first -= i / 2;
    for(int i = N-M; 0 < i; i /= 5) two_five.second -= i / 5;
    
    //위에서 구한 개수에서 M!만큼의 2와 5의 개수를 뺌
    for(int i = M; 0 < i; i /= 2) two_five.first -= i / 2;
    for(int i = M; 0 < i; i /= 5) two_five.second -= i / 5;
    
    int result;
    if(two_five.first < two_five.second) cout << two_five.first << "\n";
    else cout << two_five.second << "\n";
    
    return 0;
}

 

그 외

---

반복적으로 세번 for문이 활용되고 있으니 함수로 만들면 코드가 더 깔끔해질 것 같습니다.