백준 js 2004: 조합 0의 개수

 

 

풀이

nCm(조합)에서 끝자리 0의 개수를 구하면 된다.

조합 공식은 n! / m! (n-m)! 이다.

만약 저 조합의 값을 구하고 0을 구하려고 한다면 

원하는 답이 나오지도 않을 뿐 더러 시간 초과 걸릴 것이다.

위 값을 구하려고 한다면 Number 범위를 넘어버린다.

그렇기 때문에 각 팩토리얼 당 0의 개수를 구해서 더하고 빼주면 된다.

0의 개수를 구하기 위해서는 소인수 분해해서 5의 개수와 2의 개수를 알아야한다.

팩토리얼은 2의 개수가 항상 5보다 많거나 적기 때문에 5의 개수만 구하면 됐지만, 

조합은 알 수 없기 때문에 2와 5를 모두 구해야 한다.

 

n! / m! (n-m)!이기 때문에

n!의 2와 5의 개수를 구하고

그 값에서

m!의 2와 5의 개수를 빼고

(n-m)!의 2와 5의 개수를 빼주면 된다.

 

팩토리얼에서 5혹은 2의 개수를 구하는 방법은

const getTwoFive = (n) => {
	const two = 0;
    const five = 0;
    for (let i = 5; i <= n; i*=5) {
    	five += parseInt(n / i);
    }
    for (let i = 2; i <= n; i*=2) {
    	two += parseInt(n / i);
    }
    return [two, five]
}

 

위 루프문에 대한 설명은 아래 게시물 참고

gigibean.tistory.com/26

백준 js 1676: 팩토리얼 0의 개수

그리고 조합 공식에서 분자의 값에서 분모의 값들을 빼주고, 

2의 배수의 개수와 5의 배수의 개수를 구한 값 중 작은 값을 출력하면 된다.

전체 코드

	const fs = require("fs");
	const [n, m] = (process.platform === "linux"
	? fs.readFileSync("/dev/stdin").toString()
	: `25 12`
	)
	.split(" ")
	.map((x) => +x);
	const getTwoFive = (x) => {
	let five = 0;
	let two = 0;
	for (let i = 2; i <= x; i *= 2) {
	two += parseInt(x / i);
	}
	for (let i = 5; i <= x; i *= 5) {
	five += parseInt(x / i);
	}
	return [two, five];
	};
	const [nt, nf] = getTwoFive(n);
	const [mt, mf] = getTwoFive(m);
	const [nmt, nmf] = getTwoFive(n - m);
	const two = nt - mt - nmt;
	const five = nf - mf - nmf;
	console.log(Math.min(two, five));

view raw 2004.js hosted with ❤ by GitHub