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

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1676번: 팩토리얼 0의 개수

문제

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

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

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

접근방법

 팩토리얼 값을 계산했을 때 나오는 0의 개수를 출력하는 문제이다. 0의 개수를 어떻게 구해야할지 생각해보는 것이 핵심이다. 이 점을 인지하고 풀이로 들어가자.

풀이

 결과값에서 0이 어떻게 생기는가 생각해보자. 팩토리얼은 모두 곱의 관계를 가지고 있으므로, 10이 들어갈 때마다 0이 하나씩 추가된다. 그 말을 정리하면, 2와 5가 한쌍일 때 마다 0이 하나 추가된다. 10! 은 2, 5 ,10 (2*5)숫자를 가지고 잇으므로 0의 갯수 2개 가 된다.

 

 이러한 점을 이용하여, 나는 팩토리얼에 사용된 2와 5의 총 갯수를 구하고, 그로인해 만들어 질 수 있는 0의 개수를 구했다. N!이 주어졌을 때 0 개수를 구하는 법은 아래와 같다.

 

• N 보다 작은 모든 2의 제곱수로 나누고, 그 합을 저장한다. 
• N 보다 작은 모든 5의 제곱수로 나누고, 그 합을 저장한다.
• 두 개중 최솟값을 반환한다.

최솟값을 반환하는 이유는 10을 만드려면 두 숫자 중 적은 갯수를 가진 쪽에 맞춰야하기 때문이다. 

코드

import java.util.Scanner;

public class Main {

 
    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);

        int fac = sc.nextInt();

        System.out.println(solution(fac));
    }

    private int solution (int factorial){

        int cnt_2 =0;
        int cnt_5 = 0;
        
		//2의 9제곱은 512 이므로, N 최대값인 500보다 큼  
        for (int i = 1 ; i < 9 ; i++){

            cnt_2+= factorial/ Math.pow(2,i);
            cnt_5+= factorial/Math.pow(5,i);

        }


        int result = Math.min(cnt_2,cnt_5);



        return result;
    }

}

 2와 5중 2가 작으므로, 작은 쪽을 기준으로 N의 최대값 보다 작은 제곱수 까지만 검사한다. 이렇게 하면, 팩토리얼을 구하지 않고도 쉽게 찾아낼 수 있다.

결과

 

 

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.