[JS|구현 알고리즘] 백준 3474번. 교수가 된 현우

 

 

---

3474번: 교수가 된 현우

입력과 출력

• 입력
  • 첫째 줄에 테스트 케이스 갯수 T ( 사용하지 않기에, _으로 처리함)
  • 두 번째 줄 ~ T번째 줄의 정수를 담은 NArray (각 배열 요소의 자료형 : String)
• 출력
  • NArray의 각 요소인 N에 대하여 N!의 끝에서부터 0의 개수를 구한 값 result 출력

 

시행착오

• 일단 어떻게 최대한 쉽게 문제를 풀이할 수 있을지 깊은 고민의 시간이 필요했다.
• 끝에서부터 0의 갯수라는 것에서 10의 곱셈을 이용한 문제이며, 2 * 5의 갯수를 생각하면 된다는 것을 알고 있었지만
• N!이 아닌 N을 가지고 어떻게 접근할 수 있을까 그 접근방식을 생각해내는 것이 막막했다.

 

• 나의 시행착오 과정은 다음과 같다.

 

• 일단, 자연수들의 팩토리얼 계산표를 보면 좀 도움이 될까 해서 찾아보니 역시나 이미 각 자연수들의 팩토리얼 숫자와 그 숫자의 0의 갯수에 대하여 정리해놓은 표가 있었다.

• 위에 나타나있는 표를 보니 N!의 소인수분해를 이용하면 된다는 것을 알게되었다.N!를 소인수분해했을 때 5가 곱해지는 그 횟수를 구하면 된다는 것을 알았다.
• 특히 제일 중요한 2의 제곱수와 5의 제곱수에 대해서 보다보니 2가 곱해지는 횟수는 충분히 많아서, N!를 소인수분해했을 때 5가 곱해지는 그 횟수를 구하면 된다는 것을 알았다.

 

• 그렇다면, 숫자 N을 가지고 어떻게 N!에서 5가 곱해진 횟수를 알 수 있을까…?
• 5의 n제곱수들(5, 25, 125 등)을 가지고 이것저것 생각해보다가 무언가를 발견했다. 
  • N이 26일 경우,
    • 26!은 26 * 25 * ... * 20 * ... * 15 * ... * 10 * ... * 5 * ... * 1 ,
    • 5²는 1번, 5¹는 5번 곱해지기에
    • 26!은 5가 총 6번 곱해지는 것( 2 + 5 - 1(25 중복) )을 알 수 있었다.
  • N이 126인 경우는 어떨까?
    • 126/5³ = 1, 126/5² = 5, 126/5¹ = 25, 몫의 누적합은 31. 126!의 끝에서부터의 0의 갯수는 31개였다.
    • 즉, 

 

• 정확한 수학적 원리를 완벽하게 설명하진 못하겠지만 그래도 물고 늘어진 덕분에 큰 발견을 했다고 생각하였다.
• 문제 풀이를 위한 수학적 접근에 대한 이해가 끝났기에 코드는 바로 구현할 수 있었다.
• 결과값으로 정수형이 나와야 하기에 5로 나눈 몫의 소수점은 버렸다.

 

 

전체 코드

let fs = require('fs')
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt'
let [_, ...NArray] = fs.readFileSync(path).toString().trim().split('\n')

NArray.map((N) => {
  N *= 1
  let result = 0
  for (let u = 5; u <= N; u *= 5) {
    result += Math.floor(N / u)
  }
  console.log(result)
})