[백준] 1679 : 팩토리얼 0의 개수(JAVA)

백준 1676 자바

팩토리얼 0의 개수

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

51166

24558

20357

47.885%

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

---

방법1 - factorial 재귀함수

주의! N의 범위는 (0 ≤ N ≤ 500)로 매우 큰 수가 될 수 있다.

BigInteger로 풀어줘야 한다.

못푼다.

답은 나오지만 범위가 커지면 안되는 틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1676 {

	static int factorial(int n) {
		if (n > 0)
			return n * factorial(n - 1);
		else
			return 1;
	}

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

		String[] arr = Integer.toString(factorial(N)).split("");

		int cnt = 0;// 0을 카운트할 변수
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
			if (arr[i].equals("0"))
				cnt++;
		}

		System.out.println(cnt);
	}

}

BigInteger로 어떻게 풀어보려했으나 난 왜 BigInteger만 만나면 어려운 것일까…………………실패했다.

방법2 : 5의 배수

아니 팩토리얼을 그럼 재귀함수로 안풀면 어떻게 풀란말이야!! 라고 생각말자

출처 :https://st-lab.tistory.com/165

 

뒷자리가 0이 나오는 경우가 언제인가?

바로 2와 5가 곱해졌을 때 이다!!!!!!!!!!!!!!!!!!!

소인수분해를 해서 2와 5가 곱한다면 0이 생기는 숫자

0~4까지는 뒤에 0의 개수가 1개

5~9까지는 뒤에 0의 갯수가 2개

10~14까지는 뒤에 0의 갯수가 3개

15~24까지는 뒤에 0의 갯수가 4개

그러나

25~30까지는 뒤에 0의 갯수가 6개가 됩니다.

 

보면 5의 배수마다 0의 카운트 값이 증가하는 것을 볼 수 있다.

근데 중요한 점이 하나 있다. 바로 입력값이 25일 때는 카운트 값이 1이 아닌 2가 증가한다.

그렇기 때문에 while문으로 누적을 해줘야한다.

5의 배수만 고려하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1676 {

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

		int cnt = 0;// 0을 카운트할 변수

		// 예 N=25
		// cnt = 5, N = 5
		// cnt = 5 + 1 , N = 1
		while (N >= 5) {
			cnt += N / 5;
			N /= 5;
		}
		System.out.println(cnt);
	}

}