백준 2004

▶ 2004번 문제 - 조합 0의 개수

->조합 nCm의 값의 끝자리 0의 개수를 출력하는 문제

- 1656번( https://shinny.tistory.com/165 )처럼 nCm을 직접 계산하면 long타입 벗어나므로 nCm을 직접 계산해서는 안됨.

 

▶ 풀이방법

- n!의 2와 5의 개수 - (n-m)!의 2와 5의 개수 - m!의 2와 5의 개수를 구해 값의 끝자리 0의 개수 출력하도록 함

   ==> 1656번 문제 참고

 

- 코드1

- 아래 코드는 시간 초과 오류 발생(정확한 이유는 모르겠지만, while문이 여러번 돌아가기 때문에 시간복잡도가 증가한다고 생각이 됨.)

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Integer.parseInt(st.nextToken());
		long m = Integer.parseInt(st.nextToken());
		
		int num2 = n2(n) - (n2(m) + n2(n-m));
		int num5 = n5(n) - (n5(m) + n5(n-m));
		
		bw.write(String.valueOf(Math.min(num2, num5)));
		bw.flush();
		bw.close();
		br.close();
	}
	public static Integer n2(long a) {
		int n2 = 0;
		for(int i = 2; i <= a; i++) {
			long num = i;
			while(num % 2 == 0) {
				n2++;
				num /= 2;
			}
		}
		return n2;
	}
	public static Integer n5(long a) {
		int n5 = 0;
		for(int i = 2; i <= a; i++) {
			long num = i;
			while(num % 5 == 0) {
				n5++;
				num /= 5;
			}
		}
		return n5;
	}
}

 

 

- 코드2

- 코드1에서 사용했던 while문 방식을 위 그림과 같은 방식으로 바꿔줌

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Integer.parseInt(st.nextToken());
		long m = Integer.parseInt(st.nextToken());
		
		long num2 = n2(n) - (n2(m) + n2(n-m));
		long num5 = n5(n) - (n5(m) + n5(n-m));
		
		bw.write(String.valueOf(Math.min(num2, num5)));
		bw.flush();
		bw.close();
		br.close();
	}
	public static long n2(long a) {
		long n2 = 0;
		if(a < 2) return 0;
		for(long i = 2; i <= a; i*=2) { //while문에서 바꿔준 형태(시간복잡도↓)
			n2 += (a/i);
		}
		return n2;
	}
	public static long n5(long a) {
		long n5 = 0;
		if(a < 2) return 0;
		for(long i = 5; i <= a; i*=5) { //while문에서 바꿔준 형태(시간복잡도↓)
			n5 += (a/i);
		}
		return n5;
	}
}

 

++이번문제 또한 좀 어려웠음 ㅜ