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

1676번: 팩토리얼 0의 개수 (acmicpc.net)

1676번: 팩토리얼 0의 개수

 

1676번 : 팩토리얼 0의 개수

---

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

 

출력

---

첫째 줄에 구한 0의 개수를 출력한다.

 

---

 

생각해 볼 점

---

맨 뒷자리의 0의 개수는 곧 10의 몇 제곱인지를 묻는 것과 같습니다.

따라서, 곱해진 10의 개수를 찾는 것이 맞습니다.

 

우선, 10은 2와 5의 약수를 지니고 있으니, 2의 개수와 5의 개수를 찾아 10을 몇 개 만들 수 있는지 세면 되지만,

팩토리얼의 특성 상 2는 5에 비해 굉장히 많이 곱해지게 됩니다.

 

예를 들어, 5!은 1 * 2 * 3 * 4 * 5인데, 5가 한 번 나올 동안 2는 2와 4에서 3개가 나온 것을 알 수 있습니다.

따라서, 우리는 2의 개수는 신경 쓰지 않고 5가 몇 개 있는 지 찾으면 정답이 됩니다.

 

실제로 5!은 120이므로 5가 1개이며, 뒷자리 0의 개수가 1개입니다.

 

N!에서 5의 배수의 개수를 찾는 방법은, N을 5로 나눈 몫이 됩니다.

단, 25나 125와 같이 5의 제곱 수의 경우를 생각해야 합니다.

 

24! 까지는 24 / 5 = 4로 정답이지만

25! 부터는 25 / 5 = 5로 오답입니다.

25 자체가 5를 2개 가지고 있으므로 6개가 정답입니다.

 

즉, 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수... 을 해야하므로,

5로 나누어진 몫이 0이 될 때까지 계속 5로 나눠서 더해주면 됩니다.

 

예시)

600!

600 / 5 = 120

120 / 5 = 24

24 / 5 = 4

4 / 5 = 0

 

120 + 24 + 4 = 148

 

코드

---

 

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int five_count = 0;   //5의 갯수
    for(; N > 0; N /= 5)    //N을 5로 나눈 몫이 5의 갯수, 25로 나눈 몫이 25의 갯수 ..
    {
        five_count += N/5;        
    }
    
    cout << five_count << "\n";
    
    return 0;
}

 

그 외

---

수학 문제는 항상 점화식이나 원리를 파악하는 것이 중요한 것 같습니다.