[백준] 1676 - 팩토리얼 0의 개수

문제링크

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

문제

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

입력

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

출력

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

조건

• 시간 제한 : 2s

• 메모리 제한 : 128MB

---

해설

1부터 N까지의 수들을 곱했을 때, 그 수에 10이 몇 번 곱해질 수 있는 지를 묻는 문제이다. 10을 만들기 위해 2와 5가 사용되고, 2는 짝수에 모두 포함되어 있기 때문에, 5의 개수만 세어주면 된다. 소인수분해 했을 때 5가 포함되는 값들은 5의 배수이고, 25의 배수는 5가 2개, 125의 배수는 5가 3개 포함된다.

풀이

5의 배수, 25의 배수, 125의 배수를 헤아리는 방법은 해당 값으로 N을 나눴을 때의 몫을 더하면 된다. 2의 개수는 충분하므로, 5가 몇개 있는지가 10을 몇 번 곱할 수 있는지와 같다. 5의 개수를 출력해주면 원하는 결과를 얻을 수 있다.

int N, result = 0;
cin >> N;

result += N/5;
result += N/25;
result += N/125;

cout << result;

---

코멘트

소인수분해를 이용하는 문제. 수학 1 카테고리에 있는 문제들은 다 난이도가 그렇게 높지 않은 문제들인 것 같다.

---

코드

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, result = 0;
    cin >> N;
    
    result += N/5;
    result += N/25;
    result += N/125;
    
    cout << result;
    return 0;
}

Uploaded by Notion2Tistory v1.1.0