[python_파이썬_pass]백준_1676번_팩토리얼 0의 개수_실버5_풀이

공부하는허딩크 : https://www.youtube.com/live/ioCTBnwKKEE?feature=shared

 

일단 N!이라는 개념을 처음 봤다.

해당 문자는 수학에서 사용하는 팩토리얼 연산을 의미한다. 1~N까지 모든 정수를 곱한 값이다.

 

그런데 또 이해 안되는게 그래서 0이 아닌 숫자가 나올때 까지 0의 개수를 구하라는게 뭐지??

고민하다가 우선 1부터 10까지 곱을 해주고 출력을 해줬다.

N = 10

temp = 1

for i in range(1, N + 1):

    temp *= i

    print(temp)

#출력값

6
24
120
720
5040
40320
362880
3628800 => 최종 N!값이 있으면 뒤에서 부터 0의 개수를 구하는게 목적이다. 

 

<첫번째 시도 : 맞았습니다.>

문제를 이해하고 나서 바로 아래와 같이 코드를 구현했다.fac()함수로 구현 하지 않고 for문으로 돌려도 되는데 fac를 복습할 겸 재귀함수를 활용해서 해결했다. 다시한번 기억해보자~!

import sys

input = sys.stdin.readline

#11분 소요

#N!에서 뒤에서부터 터음 0이 아닌 숫자가 나올때까지 0의 개수

#과정이 중요한게 아니라 최종 N!의 숫자에서 0의 개수를 구하는 것

N = int(input())

def fac(n):

    if n == 0: # 다시 공부함

        return 1

    # elif n == 2:

    #     return 2 이거 필요없음

    else:

        return fac(n - 1) * n

   

answer = str(fac(N))

cnt = 0

for i in answer[::-1]:

    if int(i) == 0:

        cnt += 1

    else:

        break

   

print(cnt)

 

<다른 사람 풀이 참고>

이게 뭐냐....... 참 희한한 코드가 다 있네.......

결국 펙토리얼로 곱해지는 숫자중에 5의 배수의 개수를 찾으면 뒤에서 0의 개수를 찾을 수 있다는 말이다.

n=int(input())

cnt=0

while n>0:

    cnt+=n//5

    n//=5

print(cnt)

 

#Chat GPT설명

이 코드는 팩토리얼(N!)에서 끝자리가 0인 숫자의 개수를 구하는 알고리즘입니다. 이 문제는 팩토리얼에서 0이 몇 개 있는지를 묻는 문제로, 0의 개수는 10의 배수 개념과 관련이 있습니다.

핵심 원리:

• 10은 2 * 5로 이루어져 있습니다. 따라서, 팩토리얼에서 10이 만들어지려면 2와 5의 쌍이 있어야 합니다.
• 그런데, 팩토리얼에서 짝수는 항상 충분히 많기 때문에 5의 배수가 얼마나 있는지 세는 것이 중요합니다.
• 즉, **N!**에서 끝자리 0의 개수는 N!에 포함된 5의 개수에 의해 결정됩니다.

코드 설명:

1. cnt = 0 : 끝자리가 0인 숫자의 개수를 저장할 변수입니다.
2. while n > 0: : n이 0보다 클 때까지 계속 반복합니다.
3. cnt += n // 5 : n을 5로 나눈 몫을 cnt에 더합니다. 즉, n이 5의 배수인 수들을 찾습니다. 예를 들어, 25는 5가 두 번 곱해지므로 두 번 계산됩니다.
4. n //= 5 : n을 5로 나눈 몫으로 갱신하여, 그 다음 5의 배수를 계산합니다.
5. print(cnt) : 계산된 5의 배수의 총 개수를 출력합니다.

어떻게 0의 개수를 구하는지:

팩토리얼에서 0의 개수는 5의 배수가 포함된 개수에 달려 있습니다. 예를 들어:

• 5! = 5 * 4 * 3 * 2 * 1 = 120 : 끝자리 0이 하나 있습니다.
• 10! = 10 * 9 * ... * 1 = 3628800 : 끝자리 0이 두 개 있습니다. 이는 5와 10에 포함된 5의 배수 때문입니다.

따라서, N!에서 5의 배수들 (5, 10, 15, ...)에 들어 있는 5의 개수를 모두 더하면 끝자리 0의 개수를 구할 수 있습니다.

동작 예시:

입력: 25

• 첫 번째 반복: 25 // 5 = 5 (5의 배수가 5개 있음) → cnt = 5
• 두 번째 반복: 5 // 5 = 1 (25 안에 5가 두 번 포함됨) → cnt = 5 + 1 = 6
• 세 번째 반복: 1 // 5 = 0 → 루프 종료

출력: 6
즉, 25!에는 끝자리 0이 6개 있습니다.

결론:

이 알고리즘은 N!에서 끝자리 0이 몇 개 있는지를 구하는 효율적인 방법으로, 팩토리얼을 직접 계산하지 않고도 5의 배수를 이용해 빠르게 계산할 수 있습니다.