[파이썬] 백준 1676 팩토리얼 0의 개수 (factorial n!)

✅ 백준 문제 링크: 백준 1676번 - 팩토리얼 0의 개수

백준 1676 팩토리얼 0의 개수

1. 팩토리얼(Factorial)이란?

 

팩토리얼은 그 수보다 작거나 같은 모든 양의 정수를 곱한 값이다.

• • 팩토리얼을 나타내는 기호는 느낌표(!) 이다.
• • 예를 들어, 5! = 1 × 2 × 3 × 4 × 5 = 120 이다.

📌 팩토리얼 예시

0! = 1
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120

 

2. 파이썬에서 팩토리얼 함수 사용하기

 

파이썬에서는 math 모듈을 사용하여 팩토리얼을 쉽게 계산할 수 있다.

 

✔ math.factorial() 함수

import math

n = 5
result = math.factorial(n)
print(result)  # 출력: 120

📌 주의:

• math.factorial(n)은 n이 음수이거나 정수가 아닐 경우 ValueError를 발생시킨다.

3. 문제 해결 방법

 

이 문제에서는 팩토리얼 값을 계산한 후, 끝에서부터 연속된 0의 개수를 찾는 것이 목표다.

 

✔ 해결 과정

1. 입력된 숫자 N의 팩토리얼 값을 구한다.
2. 팩토리얼 값을 문자열로 변환하고 뒤집는다.
3. 뒤집힌 숫자를 앞에서부터 확인하며 0의 개수를 센다.
4. 0이 아닌 숫자가 나오면 반복을 종료하고, 0의 개수를 출력한다.

📌 예제 설명

• 입력값: N = 10
• 팩토리얼 값: 10! = 3628800
• 뒤집힌 값: 0088263
• 맨 앞의 연속된 0 개수: 2

4. 파이썬 코드 구현

import math

# 입력받기
N = input()

# 1. 입력된 숫자 N의 팩토리얼을 구하기
factoNum = math.factorial(int(N))

# 2. 팩토리얼 값을 문자열로 변환 후 뒤집기
reverseNum = str(factoNum)[::-1]

# 3. 뒤집힌 값에서 연속된 0 개수 세기
cnt = 0
for j in reverseNum:
    if j == '0':
        cnt += 1
    else:
        break        

# 4. 결과 출력
print(cnt)

 

5. 예제 테스트

 

✔ 입력 예시 1

10

 

✔ 출력 예시 1

2

📌 설명:

10! = 3628800 → 뒤집으면 0088263 → 연속된 0의 개수는 2개

 

✔ 입력 예시 2

3

 

✔ 출력 예시 2

0

📌 설명:

3! = 6 → 끝에 0이 없으므로 0 출력

 

6. 문제 해결 최적화

 

위 코드는 math.factorial()을 사용하여 팩토리얼을 직접 계산했지만, N이 커질수록 팩토리얼 값이 매우 커져서 연산 속도가 느려질 수 있다.

 

이 문제에서는 팩토리얼의 0의 개수를 찾기 위해 직접 팩토리얼을 계산할 필요 없이, 5의 배수 개수를 세는 방식으로 해결하는 것이 더 효율적이다.

 

🚀 더 효율적인 풀이 방법:

N = int(input())

cnt = 0
while N >= 5:
    cnt += N // 5
    N //= 5

print(cnt)

📌 왜 이렇게 해결할 수 있을까?

• 팩토리얼에서 0이 생기는 이유는 10이 곱해질 때마다 0이 하나 추가되기 때문이다.
• 10은 2 × 5로 이루어져 있는데, 2의 배수는 항상 많으므로, 5의 배수 개수만 세면 된다.
• N // 5는 5의 배수 개수를, N // 25는 25의 배수 개수를, N // 125는 125의 배수 개수를 고려한다.

✅ 이 방법을 사용하면 O(log N) 시간 복잡도로 매우 빠르게 해결할 수 있다.

 

7. 마무리

• math.factorial()을 사용하여 팩토리얼을 직접 계산하고, 문자열을 뒤집어 0의 개수를 세는 방법을 사용했다.

• 더 효율적인 방법으로는 팩토리얼의 0의 개수를 구할 때 5의 배수 개수를 세는 방식을 사용할 수 있다.