[백준/JS] 3474번 - 교수가 된 현우

Pakxe·2024년 1월 28일

JavaScript baekjoon ps

PS

목록 보기

15/16

✦ 문제

바로가기

✦ 실패한 풀이들

정석대로 펙토리얼을 구하고 0의 개수를 세는 풀이이다.

당연하게 시간 초과가 날 것이라고 예상하면서도 이 방법이 아니면 절대 모르지 않나? 라고 생각해서 그대로 진행했다. 결과는 참패

숫자가 길어서 곱셈 비용이 많이 드나싶어 0을 제거하고 곱셈하기

역시나 실패했다.

✦ 접근

어떤 수의 끝에 0이 존재하려면 어떤 값이 곱해져야 하는지 생각해보면 된다. 간단하게 과학적 표기법을 떠올리면 이해가 쉽다. 100000라는 긴 수는 10^5로, 2000은 2 * 10^3으로 표기하는 것처럼 말이다.

결국 뒤에 0이 있는 건 10이 1개 이상 곱해져있기 때문이다. 그렇다면 1~n까지를 돌면서 몇 개의 10이 존재하는지(나눠지는지) 보면 되지 않을까 싶을텐데, 10은 결국 1개의 2와 1개의 5가 있어도 만들어지기 때문에 10이 몇 개 존재하는지만 계산해서는 올바른 답이 나오지 않는다. 10!을 예로 들면 10이라는 갑은 딱 한번 곱해지지만, 2와 5도 곱해지기 때문에 n!에서 10의 개수만 세는 것은 정확하지 않다는 뜻이다.

따라서 10을 구성하는 가장 최소의 단위인 2와 5를 기준으로 몇 개의 10이 n!에 포함되어 있는지 구해보면 된다.

이때 10이 되려면 2와 5는 한 개씩 쌍을 이루어야 된다. 즉 2의 개수와 5의 개수 중 최소 개수가 최종 10의 개수가 되는 것이다.

개수 구하기

그렇다면 어떻게 n!을 소인수 분해해서 보이는 2의 개수와 5의 개수를 구할 수 있을까?

제일 간단하게는 n % 2 같은 나머지 연산으로 구할 수 있다. 하지만 나머지 연산의 비용이 큰 이유에서인지 시간초과가 발생했다.

그래서 다르게 n! = 1*2*3*4... 에서 2로 나눠지는 항의 개수를 구하는 방법을 사용했다. n!에서 2로 나눠지는 항이란 2, 4, 6, 8 ..이 된다. 그리고 2개의 2인 4로 나눠지는 항이란 4, 8, 12 ...가 된다. 3개의 2인 8로 나눠지는 항도 마찬가지로 구할 수 있다.

예로 10! = 1*2*3*4*5*6*7*8*9*10에서 2, 2^2=4, 2^3=8로 나눠지는 수의 개수를 구한다. 각각 5, 2, 1개로 총 8개이다. 이 8개는 10! = 어떤값 * 2^8이라는 뜻이며 우리가 구하려는 2의 개수이다.

다만 저렇게 각각의 개수를 구해서 더한 값이 왜 총 2의 개수냐는 의문이 들 수 있다. 2로 나눠지는 수는 2, 4, 6, 8, 10이다. 그리고 2^2로 나눠지는 수는 4, 8로 2개다. 그런데 4는 2가 2개고 8도 2가 3개인데 왜 2^2=4 과정에서 구해진 값은 2로도 충분한 것일까? 2보단 커야하지 않을까?

그 이유는 2^2=4의 이전의 2에서 이미 4와 8을 구성하는 1개의 2가 이미 계산되었기 때문이다. 마찬가지로 2^3=8에서도 1로만 계산되어도 충분한 이유는 2와 2^2=4에서 이미 8 = 2^3을 구성하는 2개의 2가 계산되었고 남은 1개의 2가 이 과정에서 마지막으로 계산되었기 때문에 1이라는 값이 나오게 된 것이다. (할부처럼.. 2를 조금씩 먼저 계산해주는)

시간을 좀 더 단축해보기

위 그림과 설명을 이해했다면 5의 개수를 구하는 것도 아주 간단할 것이다. 머릿속으로 한번 위 그림을 5의 버전으로 그려보자. 그러면 빨간 체크가 2의 그림보다 적을 것이다.

우리가 앞에서 10의 개수는 2의 개수와 5의 개수에 의존한다고 헀고, 정확하게는 2, 5의 개수 중 더 작은 개수가 10의 개수가 된다고 했다.

그런데 2와 5의 개수 그림을 그려보았다면 아주 직관적으로 5의 개수(빨간 체크)가 현저히 적다는 것을 알 수 있다. 그렇다는 것은 구태여 더 많이 존재하는 2의 개수를 구할 필요 없이 적은 5의 개수만으로도 10의 개수를 알 수 있다.

✦ 코드

function getFiveCount(n) {
  let five = 0;

  for (let i = 5; i <= n; i *= 5) five += Math.trunc(n / i);

  return five;
}

const answers = [];

for (let i = 1; i <= T; i++) {
  const num = input[i]; // Number

  const fiveCount = getFiveCount(num);

  answers.push(fiveCount);
}

console.log(answers.join('\n'));