[백준] 1676번 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

2의 배수와 5의 배수의 합집합 구할 때처럼

1) 10으로 안 나눠지는 2의 배수 (여집합)

2) 10으로 안 나눠지는 5의 배수 (여집합)

1)과 2)의 최솟값에 10의 배수를 더해주는 식으로 코드를 구현했다. (공집합)

 

# BOJ_1676

# 입력
n = int(input())

# 10의 약수는 1, 2, 5, 10이므로 1, 2, 3, ..., n이 이하의 수 중에서 10의 배수는 어차피 2, 5의 배수이므로
# 2, 5의 배수의 개수 중에 최솟값을 구하면 되겠다.
two_multiple = 0
five_multiple = 0
ten_multiple = 0
for number in range(1, n + 1):
    # 순수 2의 배수
    if number % 2 == 0 and number % 10 != 0:
        two_multiple += 1
    # 순수 5의 배수
    if number % 5 == 0 and number % 10 != 0:
        five_multiple += 1
    if number % 10 == 0:
        ten_multiple += 1
    
answer = min(two_multiple, five_multiple) + ten_multiple

print('only 2: ', two_multiple)
print('only 5: ', five_multiple)
print('10: ', ten_multiple)
print(answer)

 

하지만 바로 틀렸습니다로 나왔다.

 

알고보니, 바로! 25같은 경우는 한 수에 5가 두 번 곱해지는데

위에 내가 짠 코드에는 한 번밖에 카운팅이 안된다는 것이다.

 

따라서 결국 n!를 한 다음 그 수를 소수인 2와 5로 소인수분해 한다음

갯수의 최솟값을 구하면 되었다.

 

??? 

뭐지.. 25를 예시를 들었을 때 25!값이 너무 커서 저장이 안되는 건가..

for number in range(1, n + 1):
    factorial *= number
print(factorial)

결과가

15511210043330985984000000

15511210043330985984000000

음.. 똑같이 나오는데

# BOJ_1676

# 입력
n = int(input())

# 10의 약수는 1, 2, 5, 10이므로 1, 2, 3, ..., n이 이하의 수 중에서 10의 배수는 어차피 2, 5의 배수이므로
# 2, 5의 배수의 개수 중에 최솟값을 구하면 되겠다.
two = 0
five = 0
factorial = 1
for number in range(1, n + 1):
    factorial *= number


while(factorial % 5 == 0):
    five += 1
    factorial /= 5
print(factorial)

while(factorial % 2 == 0):
    two += 1
    factorial /= 2

이렇게 팩토리얼 값을 구하고 2와 5로 소인수분해 해주면

3.1022420086661973e+24
29 1
1

5로 6번 나눠져야 할 수가 한번만 나눠지는 걸까

 

 

이렇게 2, 5로 소인수분해하는 while문을 루프 안에 넣어주면

# BOJ_1676

# 입력
n = int(input())

# 10의 약수는 1, 2, 5, 10이므로 1, 2, 3, ..., n이 이하의 수 중에서 10의 배수는 어차피 2, 5의 배수이므로
# 2, 5의 배수의 개수 중에 최솟값을 구하면 되겠다.
two = 0
five = 0
factorial = 1
for number in range(1, n + 1):
    factorial *= number
    while (factorial % 5 == 0):
        five += 1
        factorial /= 5
        # print(factorial)
    while (factorial % 2 == 0):
        two += 1
        factorial /= 2
        # print(factorial)

print(two, five)
answer = min(two, five)
print(answer)

25
22 6
6

이렇게 값이 잘 나온다.

 

하지만 23으로 갔을 때 2의 19승으로 나와야 하는데 2의 23승으로 나와버린다.

그 이유는 바로 factorial값이 커지면서 지수표현으로 바뀌기 때문이다. (아래)

n = int(input())

# 10의 약수는 1, 2, 5, 10이므로 1, 2, 3, ..., n이 이하의 수 중에서 10의 배수는 어차피 2, 5의 배수이므로
# 2, 5의 배수의 개수 중에 최솟값을 구하면 되겠다.
two = 0
five = 0
factorial = 1
for number in range(1, n + 1):
    print("number: ", number)
    factorial *= number
    # while (factorial % 5 == 0):
    #     five += 1
    #     factorial /= 5
    #     # print(factorial)
    while (factorial % 2 == 0):
        two += 1
        print("two: ", two)
        factorial /= 2
        print("factorial: ", factorial)
print(two, five)
answer = min(two, five)
print(answer)

22!에서 23!으로 넘어올 때 숫자 표현이 지수표현으로 바뀌면서 뜬금없이 지수표현을 2로 나누게 된다.

따라서 수가 더 커지기 전에

23은 2나 5로도 안 나눠지기 때문에 곱하지 말고 그냥 버린다.

애초에 각 number를 5로 소인수분해서 다 더해주면 될 것 같다.

어차피 2를 소인수분해한 값보다 항상 5를 소인수분해해준 값이 더 적으므로!!

 

그래도 2로 소인수분해한 지수값이랑 5로 소인수분해한 지수값이랑 둘 다 구해주자

 

정답이 나온 코드

# BOJ_1676
# 입력
n = int(input())

# 팩토리얼에서 각 수를 곱해주기 전에
# 2, 5로 소인수분해해서 각각 지수값을 구한다.
two = 0
five = 0
for number in range(1, n + 1):
    while (number % 5 == 0):
        five += 1
        number /= 5
    while (number % 2 == 0):
        two += 1
        number /= 2
answer = min(two, five)
print(answer)

 

좀 더 욕심내서 단순화 한다면

n = int(input())
# 팩토리얼에서 각 수를 곱해주기 전에
# 5로 소인수분해해서 지수값을 구한다.
five = 0
for number in range(1, n + 1):
    while (number % 5 == 0):
        five += 1
        number /= 5
print(five)

으헝 드디어!!