1676 팩토리얼 0의 개수

728x90

숫자를 처음부터 주어진 최대값인 500까지 모두 곱해서는 절대 이 문제를 풀지 못한다 ㅎ

그래서 어떻게 해야 이 문제를 풀 수 있을까를 고민하던 찰나 0의 개수는 결국 2와 5가 필요한 10이 몇개 만들어지냐 라는 점을 발견 ! 그럼 0부터 N까지 중에 2와 5가 쌍으로 몇개나 있는지 확인을 해보았다.

import java.io.*;

public class Main {
	public static void main (String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //N을 받아준다
		int N = Integer.parseInt(br.readLine());
		
        //2가 몇개인지 세보기 !
		int cnt2 = 0;
        //5가 몇개인지 세보기 !
		int cnt5 = 0;
        
        //1부터 N까지 반복하면서 ~
		for(int i = 1; i<=N; i++) {
        //이번 차례의 i를 temp에 저장해주고 !
			int temp = i;
        //while 문을 통해 temp를 2와 5로 될때까지 나눠준다.
			while(true) {
				if(temp%2 == 0) {
					temp /= 2;
					cnt2++;
				}else if(temp%5 == 0){
					temp /= 5;
					cnt5++;
				}else break;
			}
		}
		
        //쌍을 이루는 2와 5들을 세줘야하기 때문에 최솟값으로 출력해주기 !
		if(cnt2 >= cnt5) {
			System.out.println(cnt5);
		}else {
			System.out.println(cnt2);
		}
	} 
}

0의 개수를 구하는 방법에 대해 고민을 조금!? 은해야 하는 문제 ㅎ