sm 기술 블로그

115. 1676(팩토리얼 0의 개수) 본문

문제/백준_자바

115. 1676(팩토리얼 0의 개수)

sm_hope 2022. 6. 27. 21:09
import java.util.*;
import java.io.*;

class Main {
	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;

		while (N >= 5) {
			cnt += N / 5;
			N = N / 5;
		}

		System.out.println(cnt);
	}
}

문제요약

팩토리얼 완료한 값에서 뒤에서부터 0이 아닌 숫자가 나올 때까지 0은 몇번 나오는가?

설명

이 문제는 설명이 그지 같다.

위 처럼 설명만 해도 이해하기는 어렵지 않았을 것이다.

예를들어 5! 은 120이고 뒤에서부터 0이 한번 나오므로 출력값은 1이다.

10! 같은 경우는 3628800이므로 0이 두번 나오므로 출력값은 2이다.

 

0의 개수는 다음과 같은 규칙이 있다.

 

2와 5가 곱해져야 0의 카운트가 증가한다.

 

따라서 5의배수! 에서 개수가 증가하는 것을 볼 수 있다.

여기서 한번 더 유의깊게 볼 점은 0의 개수는 5를 지닌 개수와 같다는 것을 볼 수 있다.

 

예를들어 20! 은 5를 4개 가지고 있다. 따라서 0의 개수는 4이다.

25! 경우 5를 6개 가지고 있다. 따라서 0의 개수는 6이다.

 

	while (N >= 5) {
			cnt += N / 5;
			N = N / 5;
		}

때문에 입력값에서 5를 나눈 몫으로 5의 개수를 구할 수 있다.

 

예를들어 25가 들어오면 25!이지만 25 / 5는 몫이 5이다.

5의 값일 경우 while문을 한번 더 진행하기 때문에 5 + 1 이되어 0의 개수는 6이된다.

 

참고

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

 

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정말 정말 쉬운 문제다. 알고리

st-lab.tistory.com

 

'문제 > 백준_자바' 카테고리의 다른 글

117. 15649( N과M(1) )  (0) 2022.06.28
116. 2004(조합 0의 개수)  (0) 2022.06.27
114. 9375 (패션왕 신해빈)  (0) 2022.06.27
113. 1010 (다리놓기)  (0) 2022.06.26
112. 11051(이항 계수 2)  (0) 2022.06.26
Comments