[백준/Node.js] 1676번: 팩토리얼 0의 개수

문제 URL: https://www.acmicpc.net/problem/1676

 

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제입니다.

 

직관적이지만 node.js 에서는 불가능한 방법

const input = require('fs').readFileSync('/dev/stdin').toString().trim()
const n = parseInt(input)

const revertToFac = function(n) {
    let fac = n
    for (let i = 1; i < n; i++) {
        fac *= i
    }
    return fac
}

const fac = revertToFac(n).toString()
let answer = 0

for (let i = fac.length - 1; i >= 0; i--) {
    if (fac[i] === '0') {
        answer += 1
    }
    else {
        break
    }
}

console.log(answer)

이 코드의 문제점

1. JavaScript 숫자 한계: n이 조금만 커져도 팩토리얼 값이 JavaScript의 안전한 정수 범위인 2^53 - 1 을 넘어갑니다. 예를 들어 25!은 15511210043330985984000000 인데, 이렇게 큰 수는 정확하게 표현할 수 없습니다. 하지만 n의 최댓값은 500이죠.
2. 비효율적: 팩토리얼을 직접 계산하고 문자열로 변환한 뒤 뒤에서부터 세는 건 시간도 오래 걸립니다.

 

올바른 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim()
const n = parseInt(input)

let answer = 0
for (let i = 5; i <= n; i *= 5) {
    answer += Math.floor(n / i)
}

console.log(answer)
```

팩토리얼을 직접 계산하지 않고, **수학적으로 0의 개수를 구하는 방법**입니다.

### 왜 이렇게 풀어야 할까?

#### 1단계: 0은 어떻게 만들어지나?

팩토리얼 끝에 0이 생기는 이유는 `10 = 2 × 5` 때문입니다.
```
5! = 1 × 2 × 3 × 4 × 5 = 120
```

2와 5가 만나서 10이 되고, 10은 끝에 0을 만듭니다.
```
10! = 1 × 2 × 3 × ... × 10 = 3,628,800

 

팩토리얼에서 2의 개수는 항상 5의 개수보다 많습니다. 짝수(2, 4, 6, 8...)가 5의 배수(5, 10, 15...)보다 훨씬 많으니까요.

따라서 5의 개수만 세면 됩니다.

 

그런데 25(5^2), 125(5^3) 같은 수는 어떻게 처리할까요?

여기가 핵십입니다!

 

n = 25일 때를 생각해봅시다:

• 5의 배수: 5, 10, 15, 20, 25 -> 5개
• 그럼 0이 5개? 아닙니다! 6개입니다.

왜냐하면 25 = 5 x 5 이기 때문이죠. 25는 5를 2개 가지고 있어서 0을 하나 더 만들어냅니다.

마찬가지로 125는 5 x 5 x 5 는 5를 3개 가지고 있습니다.

 

// i = 5: 5의 배수가 몇 개?
Math.floor(25 / 5) = 5  // 5, 10, 15, 20, 25

// i = 25: 25의 배수가 몇 개?
Math.floor(25 / 25) = 1  // 25 (5를 하나 더 가지고 있으니 +1)

// i = 125: 125의 배수가 몇 개?
Math.floor(25 / 125) = 0  // 없음

// 답: 5 + 1 + 0 = 6개

 

정리

• 5로 한 번 나눠지면 -> 0 한 개 기여
• 25로 나눠지면 -> 0 한 개 더 기여
• 125로 나눠지면 -> 0 한 개 더더 기여

이렇게 5의 거듭제곱으로 계속 나누면서 각 단계에서 몇 개씩 기여하는지 세어 더하면, 팩토리얼을 직접 계산하지 않고도 정답을 구할 수 있습니다.

 

시간복잡도는 O(log N)으로, 매우 효율적입니다.