[JAVA][BOJ][S5] 1676. 팩토리얼 0의 개수

1676번: 팩토리얼 0의 개수

문제

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

입력

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

출력

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

풀이

처음에는 무식하게 팩토리얼 값을 구한 뒤 0의 값을 구해 보려고 했지만 20만 넘어가도 long으로는 담을 수가 없다 나머지 연산을 이용해 뒷부분만 뽑아 보려고 했지만 그마저도 넘어간다 이 문제는 팩토리얼 값을 구하는 문제가 아니라 소인수분해를 잘 이용하는 문제에 가깝다

가장 뒷자리가 0이 되기 위해서는 2*5의 합이 있어야 하는데, 2는 무조건 짝수에 포함되어 있기 때문에 5가 몇 번 들어갔는지만 계산해 주면 된다 때문에 값을 5로 나눠 준 뒤 5의 제곱수(25, 125등)에서 계속해서 나눠주는 방식을 사용했다

코드

package 문제풀이;

import java.io.*;
import java.util.*;

public class S5_1676_팩토리얼0의개수 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int ans = 0;

		while(true) {
			if(N < 5) break;
			ans += N/5;
			N /= 5;
		}
		
		System.out.println(ans);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘