1676. 팩토리얼 0의 개수

백준 1676번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1676번: 팩토리얼 0의 개수

문제

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

입력

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

출력

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

풀이

아이디어

500팩토리얼은 숫자 자료형으로 담기에는 너무 큰 수이기 때문에 절대 팩토리얼을 직접 구해서 0의 개수를 구하는 문제는 아니다.

숫자의 끝에 0이 몇개가 될 지 여부는 이 수를 인수분해했을 때 10이 몇번 곱해져있는지를 확인해보면 알 수 있다.

따라서 1부터 N까지 각각의 수를 곱셈으로 표현했을 때 (즉 인수분해) 2가 곱해지는 횟수와 5가 곱해지는 수를 세서 더 작은 수를 구해주면 그것이 바로 N!에서 뒤에서 처음 0이 아닌 숫자가 나올 때까지의 0의 개수가 될 것이다.

(같은 제목의 더 난이도가 높은 문제도 있다. 일단 이 1676번은 최대 500팩토리얼로 비교적 N의 크기가 작은 편이라 이렇게 일일이 곱해지는 2와 5의 개수를 구해줘서 문제를 풀 수 있었지만 동명의 다른 문제는 N의 최댓값이 100,000,000이기 때문에 같은 방법으로는 풀 수 없을 것 같다. … 그 다른 문제는 아직 안풀어봤기 때문에 다음에 풀게 되면 여기 추가하겠다.)

코드

/*
2022-1-30
1676_팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676
*/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int cnt2 = 0, cnt5 = 0;
    int N, temp;

    cin >> N;
    for (int i = 1; i <= N; i++){
        temp = i;
        while ((temp % 2) == 0){
            cnt2++;
            temp /= 2;
        }
        temp = i;
        while ((temp % 5) == 0){
            cnt5++;
            temp /= 5;
        }
    }

    cout << min(cnt2, cnt5);

    return (0);
}