[JAVA] 백준 2004번

2004번 - 조합 0의 개수

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] numbers = br.readLine().split(" ");
		long n = Long.parseLong(numbers[0]);
		long m = Long.parseLong(numbers[1]);

		int twoCount = 0; // 2의 개수
		int fiveCount = 0; // 5의 개수

		for (long i = 2; i <= n; i = i * 2) { // 2의 개수를 구하는 반복문

			twoCount = (int) (twoCount + n / i);

			if (i <= m) {
				twoCount = (int) (twoCount - m / i);
			}

			if (i <= n - m) {
				twoCount = (int) (twoCount - (n - m) / i);
			}

		}

		for (long i = 5; i <= n; i = i * 5) { // 5의 개수를 구하는 반복문
			fiveCount = (int) (fiveCount + n / i);

			if (i <= m) {
				fiveCount = (int) (fiveCount - m / i);
			}

			if (i <= n - m) {
				fiveCount = (int) (fiveCount - (n - m) / i);
			}

		}

		bw.write(String.valueOf(Math.min(twoCount, fiveCount))); // 2, 5중 더 작은 개수를 출력

		bw.flush();
		bw.close();
	}

}

 

처음 문제에 접근한 방식

1. 0이 생성되는 경우는 2 * 5 가 있는경우로 이전 문제처럼 5의 개수만 카운트함

2. 분모의 5의개수 - 분자의 5의개수를 입력 후 출력했지만 오답 ex)5C4 

3. 2의 개수도 함께 구해서 반복문을 통해 오름차순으로 카운트했지만 시간초과발생

 

정답을 맞춘 풀이방법

1 . 입력된 수를 2의 배수, 5의 배수들로 각각 나누어 준후 그값을 더해서 카운트함

2. 분모의 경우 개수를 더하고, 분자의 경우 값을 빼줌

3. 최종적으로 2의 개수와 5의 개수를 출력

 

※반복문을 2의배수, 5의배수로 나누는 이유

- 각각의 배수로 나눈 몫이 각각의 배수가 들어있는 개수이다

ex)입력된 값이 10인경우

2 4 6 8 10

10 / 2 = 5개(2 4 6 8 10)  :  2의 배수가 5개임

10 / 4 = 2개(4 8) :  4의 배수가 2개임

10 / 8 = 1개 (8 ) :  8의 배수가 1개임