백준 2004번_조합 0의 개수_java

문제

접근방식

끝자리가 0이 되기 위해서는 10의 배수여야 하고 10의 배수는 2의배수 이면서 5의 배수이다.
n이 250일 경우 5를 약수로 가지는 개수는 아래의 표와 같이 5의 배수의 수 + 25의 배수의 개수 + 125의 배수의 개수의 합과 같다.

5
25 = 5*5
125 = 5*5*5

	5	10	15	20	25	50	125	250
5의 배수	1	1	1	1	1	1	1	1
25의 배수					1	1	1	1
125의 배수							1	1

250!의 5를 약수로 가지는 수는 위의 표를 참고하면 250/5 + 250/25 + 250/125가 된다.
결과값은 (n!의 5를 약수로 가지는 수 - r!의 5를 약수로 가지는 수 - (n-r)!의 5를 약수로 가지는 수) 와 (n!의 2를 약수로 가지는 수 - r!의 2를 약수로 가지는 수 - (n-r)!의 2를 약수로 가지는 수) 중에 최소값을 구하면 된다.

코드

package acmicpc;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class acmicpc2004 {
	public static void main(String[] agrs) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
			
			int intArr[] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			int n = intArr[0];
			int m = intArr[1];

			int answer[][] = {{n, 0, 0}, {n-m, 0, 0}, {m, 0, 0}}; //num, 5 약수개수, 2 약수개수
			int cnt = 0;
			
			if(m >= 1) {
				for(int i=0; i<3; i++) {
					int num = answer[i][0];
					cnt = 0;
					int jisu = 1;
					
					//5 약수개수
					while(true) {
						int quotient = num / (int)Math.pow(5, jisu++);
						if(quotient > 0) {
							cnt += quotient;
						} else {
							answer[i][1] = cnt;
							break;
						}
					}
					
					cnt = 0;
					jisu = 1;
					
					//2 약수개수
					while(true) {
						int quotient = num / (int)Math.pow(2, jisu++);
						if(quotient > 0) {
							cnt += quotient;
						} else {
							answer[i][2] = cnt;
							break;
						}
					}
				}
				
				writer.append(String.valueOf(Math.min(answer[0][1] - answer[1][1] - answer[2][1], answer[0][2] - answer[1][2] - answer[2][2])));
			} else if(m < 1) {
				writer.append(String.valueOf(cnt));
			}
			
			writer.flush();
			writer.close();
		} catch (Exception e) {
			
		}
	}
}