[백준 1676 파이썬] 팩토리얼 0의 개수 (실버4, 정수론)

알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : △ (풀이 참고 후 최적화)

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

SOLVE 1

팩토리얼 쫙 펼쳐서 나열해봤을 때, 2와 5의 개수에 관한 규칙 찾고 활용

import sys
input = sys.stdin.readline

N = int(input())

count = 0
while N >= 5:
    count += N//5
    N //= 5
    
print(count)

SOLVE 2

1부터 N까지 for 돌면서 각 수마다 2와 5의 개수 카운팅, 2와 5의 총 개수 중 더 작은 값이 답

N = int(input())
c_2 = 0
c_5 = 0

# 1부터 N까지 모든 수를 for 순회
for n in range(1, N+1):
    # n을 소인수분해 했을 때, 2의 개수를 카운팅
    while True:
        if n % 2 == 0:
            n /= 2
            c_2 += 1
        else:
            break
    
    # n에서 x2를 다 빼내고 남은 수에 대해 5의 개수를 카운팅
    while True:
        if n % 5 == 0:
            n /= 5
            c_5 += 1
        else:
            break

# 2의 차수와 5의 차수 중 작은 것을 선택, 그 수만큼이 10이 포함된 개수이자 0의 개수이다.
print(min(c_2, c_5))

SOLVE 1) 풀이 요약 (팩토리얼 쫙 펼쳐서 나열해봤을 때, 2와 5의 개수에 관한 규칙 찾고 활용)

1. 너무 헬이었다. 최적화 풀이이고 2004번 문제를 풀 때 반드시 활용해야하는 풀이인데, 원리를 이해하는게 너무너무 어려웠다.

2. N!의 일의 자리 수부터 0이 아닌 수가 나올 때까지 0의 개수는, N!의 x10의 개수이다. 그리그 그 것은 소인수분해 했을 때 2와 5의 쌍의 개수, 즉 2와 5의 지수 중 작은 값이 0의 개수와 같다.

3. 한 편, 1!, 2!, 3! 순차적으로 1, 2, 3을 곱해나가면서 다음 팩토리얼을 만들 수 있다. x2의 개수는 짝수를 새로 곱해줄 때마다 늘어나고, x5의 개수는 5의 배수를 새로 곱해줄 때마다 증가하므로, 직관적으로 봐도 항상 2의 지수가 5의 지수보다 크다. 제곱수의 경우엔 카운트를 더 많이 해줘야 하는데, 이 것도 직관적으로 보면 마찬가지로 1부터 어떤 수까지, 2의 제곱수가 훨씬 크게, 많이 등장한다.

   그래서 2의 개수를 구할 필요 없이, 5의 지수만 구하면 그게 구하는 0의 개수와 같다.

   구하는 답 = N!을 소인수분해했을 때 기준으로, 5의 지수 값.

4. N!을 소인수분해하기는 어려우므로, 그냥 1부터 N까지의 곱을 쫙 펼쳐놓고 그걸로 생각을 해보자.

   우선 N!말고 N을 가지고만 생각해보자. 만약 N=36이면, 1부터 N까지 연속된 수들 중에서 5의 배수가 5부터 35까지 7개 있다. 단순히 그 개수만을 카운팅하면 5개이다. (5의 배수의 개수)

   x5, x10, x15, x20, x25, x30, x35 (다들 소인수분해해도 5가 1개 들어있음)

5. 그런데 제곱수의 경우에는 25=5x5처럼, 하나의 수에 5개가 여러 개 들어있으므로 이 경우를 따로 더 카운팅을 마저 해줘야한다. (제곱수의 배수들에 대해 덜 한 카운팅을 마저 더 해줘야한다.)

   예를 들어, N=260인 경우를 생각해보자.

   먼저 N//5를 계산하면 50개(5의 배수의 개수)이다. count에 더해주자.

   다음으로 N//25를 계산해보면 10개(25의 배수의 개수)이다. 이걸 그대로 count에 더해주면 된다. 각 25의 배수 수에 대해 2개의 카운팅 중 하나는 앞서 5의 배수 카운팅에서 한 번 해줬기 때문이다.

   마찬가지 원리로 N//125를 그대로 count에 더해준다. (값은 2인데, 1부터 260까지 등장하는 125의 배수의 개수이고, 3개의 카운팅 중 2개는 앞서 5의 배수, 25의 배수 카운팅에서 이미 했으므로 한 번만 더해주면 되고, 이는 그냥 125의 배수의 개수만큼과 같은 값이라서 이만큼만 더해주고 따로 뭘 더 안해줘도 되는 것)

6. 더 이상 다음 제곱수로 나눈 몫이 없을 때까지 반복해주면 총 카운팅이 구해진다.

   이 로직을 while문으로 구현하면 된다.

7. count에 N//5를 더해주고, 그 다음 N//25, N//125를 계속 더해주기 위해 N을 N//=5로 갱신해준다.

   어느 순간 N<5가 되면 그 것은 1부터 N까지 등장하는 모든 제곱 수를 카운팅해준 상태이다.

SOLVE 2) 풀이 요약 (1부터 N까지 for 돌면서 각 수마다 2와 5의 개수 카운팅, 2와 5의 총 개수 중 더 작은 값이 답)

• 끝에서부터 0이 아닌 수를 만날 때 까지의 0의 개수를 구하는 법은, 소인수분해 했을 때 2의 개수와 5의 개수 중 작은 것을 골랐을 때, 그 수가 답이다. 0의 개수는 곧 x10이 몇개 있느냔데, 10은 2와 5의 곱이기 때문

배운 점, 어려웠던 점

• 실버4 문제 맞나.. 원리 이해하는데도 겁나 어려웠다(최적화 풀이)

  수학적 지식이 핵심인 문제였다... 너무 어려운거 아닌가요!!

• 배운 수학적 원리 요약 : N!의 뒤에서부터 0의 개수, 즉 x10의 개수는 x5의 개수와 같고, 이 개수를 구하는 방법은, N//5 + N//25 + N//125 +.... 이다. (5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수)

  5부터 시작해서, 5의 배수의 개수는 그 뒤 25, 125, 625... 등의 개수와 하나 겹치고, 25의 배수의 개수는 그 뒤에 125, 625,...등의 개수와 한 번 겹치고, 이런 식으로 가기 때문에 그냥 5, 25, 125,...의 배수의 개수만을 더해주면 된다.

• 이 문제의 어려운 점은 두가지이다.

  • 팩토리얼 소인수분해 시 2의 지수가 5의 지수보다 항상 크다는 규칙을 발견하는 것

  • 5의 지수를 구하기 위해 5로 나눈 몫(1부터 N까지 5의 배수의 개수), 25로 나눈 몫(1부터 N까지 25의 배수의 개수, 제곱수는 그 지수만큼의 5를 갖고 있음), ..., 를 더해주는 아이디어를 생각하는 것