[백준 1676번 팩토리얼 0의 개수 - node.js] [알고리즘 기초 1/2]

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

1676번: 팩토리얼 0의 개수

 

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

 

첫째 줄에 구한 0의 개수를 출력한다..

 

예제 입출력

 

입력	출력
10	2

 

풀이[node.js]

 

 

728x90

팩토리얼에서 뒤에 0이 나오려면 10이 곱해져야 한다.

10이 구해지려면 2나 5의 개수를 구해서 최소값을 구해야하는데, 이말은 즉, 2가 3개 5가 2개인 경우, 2와 5가 페어로 있어야 10이 되므로, 0은 2개가 된다.

 

그러므로, 원래 정석은 아래와 같이 2와 5의 개수를 각각 구해, 적은 수를 출력해줘야하는데, 결국 2의 배수는 5의 배수보다 많기 때문에 5의 배수를 구하는게 최소값이 되므로 위에서는 5의 배수만을 구했다.

 

5의 배수를 구하는 방법만 설명을 해보자면, 들어온 값이 25일 경우, 25까지 5의 배수는 6개가 된다. (5, 10, 15, 20, 25<-5가 2개)

25를 5로 나누면 간단히 5의 배수가 5개가 나오지만, 25에서의 5가 2번이 나오는데, 이 값을 구하지 못하게된다.

그래서, 25를 5로 나눈 후, 5로 다시 나누어주면, 5+1개로 6개라는 정확한 값이 나온다.

이 방식을 구현하기 위해, inputs5를 5로 나누어준 값을 answer에 넣어주고, 다시, inputs을 5로 나누고 그래도 그 값이 5보다 크다면 다시 5로 나누어서 answer에 값을 넣어주는 것이다.

 

다시 30을 간단히 예로 구해보자.

5의 배수의 개수를 구하려면 30/5 = 6으로 구할 수 있을 것이다.

하지만, 25와 같은 경우가 있다는 것을 명심하자. 아래를 보면 30을 25로 나눈 값이 6이 나온 것을 알 수 있다.

이는 5보다 큰 수 이므로, 6 / 5를 하면 다시 5의 배수가 하나 더 나오게 된다.

 

이는 결국, 30을 25로 나눈 것으로, 30/ 25를 5의 배수로 나누면 6 / 5를 구하는 것으로, 이는 30을 25로 나눈 것과 같다는 것을 알 수 있다.

30 / 25 = 6 / 5 = 1

위와 같은 논리로 아래와 같은 코드를 구현한 것이다.

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString();
var inputs5 = Number(inputs);
var inputs2 = Number(inputs);
var answer5 = 0;
var answer2 = 0;
while(inputs5 >= 5){
	answer5 += parseInt(inputs5 / 5);
	inputs5 /= 5;
}

while(inputs2 >=2){
    answer2 += parseInt(inputs2 / 2);
    inputs2 /= 2;
}
console.log(Math.min(answer5, answer2));