[백준] 1676 팩토리얼 0의 개수

[Silver 5] 1676 팩토리얼 0의 개수

문제 링크

구분

알고리즘 분류 > 수학

풀이 요약

5의 배수가 몇 개 있는지 세는 문제

나의 풀이

// 정답 풀이
const input = require("fs").readFileSync("/dev/stdin").toString().trim();
let N = Number(input);
let count = 0;

for (let i = 5; i <= N; i *= 5) {
  count += Math.floor(N / i);
}

console.log(count);

// 틀린 풀이
const input = require("fs").readFileSync("/dev/stdin").toString().trim();
let N = Number(input);
let temp = [];
let count = 0;

while (N > 0) {
  temp.push(N);
  N = N - 1;
}
let sum = String(temp.reduce((a, b) => a * b));
sum.split(" ");
for (let i = 0; i < sum.length; i++) {
  if (sum[i] == 0) {
    count++;
  }
}
console.log(count);

처음에는 틀린 풀이로 제출했다가 통과하지 못했습니다. 이유는 팩토리얼은 매우 큰 수이기 때문에 Number가 감당할 수 없다고 합니다.

그래서 위의 정답풀이를 생각하게 되었는데 팩토리얼은 N부터 1까지의 수를 모두 곱하게 되고 팩토리얼을 계산하면서 0이 생기는 조건은 10이 곱해질 때마다 0이 생기고 2*5가 만날 때마다 0이 붙습니다.

따라서, 팩토리얼을 곱할 때 2는 2이상의 수라면 무조건 곱해지고 5를 찾는 것이 핵심이라고 생각했고 5의 배수가 몇 번 등장하는지를 세게 되었습니다.

 

예를 들어, 5! 이 있을 때 54321= 120 (0의 개수: 1개)

5가 한번 등장했기 때문에 0의 개수가 1개입니다.

10! = 1098765432*1 = 3628800 (0의 개수: 2개)

10과 5에서 5가 두번 등장하기 때문에 0의 개수가 2개입니다.

배운 점

꼭 팩토리얼 문제라고 해서 팩토리얼 점화식을 쓸 필요가 없다는 것을 배웠습니다. 그리고 팩토리얼은 기하급수적으로 커지는 수이기 때문에 Bigint를 활용한 풀이도 알게 되었습니다.

실제로 같은 node.js 언어를 사용하여 문제를 풀이한 사람들의 코드길이는 300~600KB 가까이 되는 것을 확인했는데 5의 배수로 count 하게 되니 200KB로 효율적으로 문제를 풀었다는 느낌을 받았습니다. 코테 문제를 풀면서 처음으로 문제에서 의도한 바를 맞춘 기분이 들었습니다. 문제를 자주 풀어 문제의 핵심을 파악해야겠습니다.