백준 1676- 팩토리얼 0의 개수, 2004- 조합 0의 개수

1676번 문제는 주어지는 숫자가 500이하이므로 그냥 팩토리얼을 구하여 10으로 나눠주면서 갯수를 세서 풀었었다.

하지만 원리를 이해하지 못하고 노가다로 푸니까 응용문제인 2004번을 풀지 못하였다.

그래서 더 최적화된 풀이로 1676번을 다시 진행하고자 한다.

 

1.언제 끝에 0이 붙나? => 10이 곱해질 때마다 0이 붙는다.

N!의 일의 자리 수부터 0이 아닌 수가 나올 때까지의 0의 갯수는 N!의 10의 갯수이다.

 

2. 10을 소인수분해하면 2와 5로 이루어져 있다.

팩토리얼 소인수분해 시, 직관적으로 항상 2의 지수가 5의 지수보다 크다는 것을 알 수 있다.

따라서, 더 작은 갯수인 5에 초점을 맞춰 10의 갯수가 아닌 5의 갯수를 구해주면 된다.

 

3. 그럼 5의 갯수를 어떻게 구할까?

5가 어디에 들어있는지 생각해보자. ==> 당연히 5의 배수마다 들어있다.

예를들면)

5, 10, 15, 20, 25, 30, 35 ...

25를 제외하고는 5가 1번씩 들어있다.

N!은 1부터 N까지를 모두 곱하는 것인데 1x2x3x4x5x6x7x8x9x10x11x12x13....

5의 갯수를 구하려면 사실상 5의 배수가 몇 개인지만 구하면 된다. ==> 5로 나누었을 때 몫

 

4. 3번에서 알 수 있듯이, 5의 제곱수(25, 125, 625...)에는 추가적으로 더 카운팅해주어야한다.

따라서 25의 배수의 갯수, 125의 배수의 갯수, 625의 배수의 갯수...를 추가적으로 모두 더해줘야 5의 갯수를 정확하게 구해줄 수 있다.

25의 배수는 5x5xn(n은 자연수)이므로 5가 2번 들어가고,

125의 배수는 5x5x5xn(n은 자연수)이므로 5가 3번 들어간다.

25는 5에서 이미 한 번 카운팅했으니 그냥 25의 배수의 갯수를 구해주면 되고

125는 5와 25에서 한 번씩 카운팅해줬으니 125도 그냥 125의 배수의 갯수를 구해주면 된다.

625도 마찬가지로 5와 25와 125에서 한 번씩 카운팅해줬으니 625도 그냥 625의 배수의 갯수를 구해주면 된다.

=> 제곱수도 5와 같이 제곱수의 배수가 몇 개인지만 구하면 된다.

 

위의 1~4를 바탕으로 하여 코드 구현

 

n = int(input())
a= 5
cnt = 0
while True:
    cnt+= n//a
    a =a*5 # 제곱수로 나눠주기 위해서 5씩 곱해줌
    if a>n: # 제곱수가 주어진 숫자보다 클 경우
        break
print(cnt)

 

 

 

2023.01.04 복습을 진행하다가 로직 이해가 어려워서 조금 더 자세하게 풀이한 설명 첨부함

 

 

 

 

 

1676에서 배운 원리를 가지고 2004를 풀어보자.

 

팩토리얼이 아닌 조합의 0의 갯수를 구하는 문제이다.

조합 식을 보면 팩토리얼을 팩토리얼로 나눠 구하는 것임을 알 수 있다.

1676번의 팩토리얼의 0의 갯수를 구하는 문제는 직관적으로 2의 지수가 5의 지수보다 크므로 5의 갯수를 구하면 됐었다.

하지만, 조합은 나눠주므로 2가 더 클수도, 5가 더 클수도 있으므로 각각 다 구해줘야 한다.

 

풀이 단계를 다음과 같다.

1. 어떠한 숫자를 카운트하는 함수 생성

주의) 제곱수도 구해야하므로 제곱수의 기본값을 mul에 두고 나누는 수에 mul을 곱해나가면서 제곱수로 만들 것

 

2. n에 대한 카운트 - r에 대한 카운트 - (n-r)에 대한 카운트 

나누기는 지수의 뺄셈이므로 조합 식에 대한 식을 작성하면 위와 같다.

 

3. 2와 5가 짝을 이뤄 10이 된다. 2와 5의 갯수가 서로 같지 않다면, 더 작은 값이 10의 갯수가 된다.

따라서, 2로 카운트한 것과 5로 카운트한 것의 최소값이 결과값이 된다.

=> min(2카운트, 5카운트)

 

위의 1~3을 바탕으로 하여 코드 구현

def cnt(a, b):
    cnt = 0
    mul = b
    while True:
        cnt += a//b
        b *= mul
        if b>a:
            break
    return cnt

n, m = map(int, input().split())
print(min(cnt(n,2)-cnt(m, 2)-cnt(n-m, 2),cnt(n,5)-cnt(m, 5)-cnt(n-m, 5)))