조합 0의 개수

두개의 숫자를 입력받고 0의 개수를 출력하는 문제이다.

문제 이미지

10의 개수가 나오려면 2와 5의 개수를 파악해야 한다고 알고 있었다.

그래서 모든 숫자를 순회하면서 5의 개수와 2의 개수를 파악하고 그중 적은 숫자를 출력해 주었다. => 바로 시간초과 였다.

고민 끝에 찾아낸 방법이다.(이미 다들 알고있는 방법이다)

10!에서 2의 개수를 찾아내는 방법은 아이패드로 그린 이미지로 대체하려합니다.

(글씨가 옥에티 이긴한데 고쳐야겠지요....)

python 코드

def divide_by_two(num) :
  body = 0
  while (num) :
    body += num // 2
    num //= 2
  return body

def divide_by_five(num) :
  body = 0
  while (num):
    body += num // 5
    num //= 5
  return body

n, m = map(int, input().split())

count_five = divide_by_five(n) - divide_by_five(m) - divide_by_five(n - m)
count_two = divide_by_two(n) - divide_by_two(m) - divide_by_two(n - m)

print(min(count_five, count_two))

js 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split(' ');
const n = +input[0];
const m = +input[1];

const divide_by_five = function(num) {
  let body = 0;
  while(num) {
    body += ~~(num / 5);
    num = ~~(num / 5)
  }
  return body;
}

const divide_by_two = function (num) {
  let body = 0;
  while (num) {
    body += ~~(num / 2);
    num = ~~(num / 2);
  }
  return body;
};

const count_five = divide_by_five(n) - divide_by_five(m) - divide_by_five(n - m);
const count_two =
  divide_by_two(n) - divide_by_two(m) - divide_by_two(n - m);
console.log(Math.min(count_five, count_two))

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