본문 바로가기
알고리즘 스터디/백준 알고리즘 기초 1

[백준 2004번 조합 0의 개수 - node.js] [알고리즘 기초 1/2]

by 레일라오리덕 2021. 8. 10.
728x90

https://www.acmicpc.net/problem/2004

 

2004번: 조합 0의 개수

첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.

www.acmicpc.net

 

문제

 

( n  )

(  m )의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 정수 nm (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

 

출력

 

첫째 줄에 (n m)의 끝자리 0의 개수를 출력한다.

 

예제 입출력

 

입력 출력
25 12 2

 

풀이[node.js]

 

 

728x90

이전의 팩토리얼 0의 개수와 문제푸는 방식은 같습니다.

다만 조합의 공식인 n! / r! (n-r)!에 맞춰서 풀어야하므로, n!, r!, (n-r)!에서의 5의 개수, 2의 개수들을 각각 구해준 후, answer2와 answer5에 각각 배열의 형태로 넣어주었습니다.

그 후, n!의 5의 개수 - ( r!의 5의 개수 + (n-r)!의 5의 개수)를 구하고, 2의 개수도 각각 구해준 후, 각각의 값들을 result2와 result5에 넣어준 후, 최소값을 출력해주면 됩니다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split(' ').map(x=> Number(x));
inputs.push(inputs[0] - inputs[1]);
var answer2 = [];
var answer5 = [];
for(var i=0; i<inputs.length; i++){
    var n5 = Number(inputs[i]);
	var n2 = Number(inputs[i]);
    var answer5N = 0;
	var answer2N = 0;
    while(n5>=5){
        answer5N += parseInt(n5/5);
		n5 /= 5;
	}
    answer5.push(answer5N);
	while(n2>=2){
    	answer2N += parseInt(n2/2);
    	n2 /= 2;
	}
    answer2.push(answer2N);
}
var result2 = answer5[0] - (answer5[1]+answer5[2]);
var result5 = answer2[0] - (answer2[1]+answer2[2]);
console.log(Math.min(result2, result5));
728x90

댓글