🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]2004번 - 조합 0의 개수

2004번 - 조합 0의 개수

문제

$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.

출력

첫째 줄에 $n \choose m$의 끝자리 $0$의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2


해결할 방법을 생각해보자.💡

팩토리얼 함수를 만들어서 풀어봤더니 런타임 에러가 났다. 이것은 입력에 n과 m의 값의 범위가 2,000,000,000까지 존재해서 너무 크기 때문이다. 이 문제 또한 도저히 어떻게 풀지 감이 안와서 구글링을 해보니 사람들 대부분이 이렇게 문제를 풀었다.

우리 함께 4200이라는 수를 소인수분해 해보자. 2가 3개, 5가 2개, 3이 1개, 7이 1개 있다.

0이라는 수가 곱셈에서 생기려면은 2와 5가 곱해져야 생긴다. 즉, 2와 5가 짝이 이루어지면 10이 된다는 뜻이며, 이 두 수 중에 적은 개수가 10의 개수와 같다는 의미이다.

위의 4200도 보자. 5가 2개, 2가 3개로 5가 1개 적다. 그래서 10이 2개 존재하는 것이고 10에 10을 곱하면 100으로 00이 두개가 생기는 원리로 이해하면 좋을 것 같다.

그래서 다른 사람들의 풀이를 참고해서 2로 계속 나누어 몫을 구하는 함수와 5로 계속 나누어 몫을 구하는 함수를 정의한 후에, n, m, (n-m)의 경우에 해당 함수들을 적용시켜 주었다.

그리고 nCk의 식을 생각하여 개수들을 빼주고, 2와 5중에서 작은 수를 출력해주면 문제를 해결할 수 있다.

이러한 창의적인 생각을 어떻게 하는 것일까?.. 수학공부를 해야하는 것인지 참.. 어렵다.

코드 💻

import sys

n, m = map(int, sys.stdin.readline().split())

def two(n):
  count = 0
  while n:
    n //= 5
    count += n

  return count

def five(n):
  count = 0
  while n:
    n //= 2
    count += n

  return count

print(min(two(n)-two(m)-two(n-m), five(n)-five(m)-five(n-m)))

해결 로그

문제 푼 날짜 체크
2022-08-08 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑