-
[백준] 1676번 : 팩토리얼0의개수 - 자바(JAVA)알고리즘/백준 2022. 9. 2. 00:01728x90
https://www.acmicpc.net/problem/1676
문제 해석
N!이 값이 가지는 0의 개수를 구해야 합니다.
만약 N!이 값이 1234000이라고 가정하면 0의 개수는 3개입니다.
문제 풀이 전 설계
1234000을 분리하면 1234 * 1000 으로 분리할 수 있습니다.
이것 또 분리하면 1234 * 10 * 10 * 10 으로 분리할 수 있습니다.
즉, 0의 개수는 10의 개수와 동일합니다.
또한 10은 2 * 5입니다.
결국 우리는 N!의 수가 2^x * 5^y 가 몇 개 나오는지 찾고 Math.min(x, y)를 하면 정답이 나오게 됩니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public 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 twoCount = 0; int fiveCount = 0; int cur = 0; for(int i=N; i>=1;i--){ cur = i; while(cur%2 == 0){ cur = cur/2; twoCount++; } while(cur%5 == 0){ cur = cur/5; fiveCount++; } } int result = Math.min(twoCount,fiveCount); System.out.println(result); } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 11286번 : 절댓값 힙 - 자바(JAVA) (0) 2022.09.05 [백준] 1107번 : 리모컨 - 자바(JAVA) (0) 2022.09.03 [백준] 7662번 : 이중우선순위큐 - 자바(JAVA) (0) 2022.09.01 [백준] 1697번 : 숨바꼭질 - 자바(JAVA) (0) 2022.08.31 [백준] 2630번 : 색종이만들기 - 자바(JAVA) (0) 2022.08.30