[백준/알고리즘/python/java] 1676번 - 팩토리얼 0 의 개수

이미지를 누르면 문제링크를 보실 수 있습니다.

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

시간제한이 2초여서 팩토리얼 함수를 재귀로 구현해도 무방한 문제 같았다.

주어진 n 에 따라 팩토리얼 함수로 n! 구하고

그 n! 을 string 화시켜서 뒤에서부터 0의 개수를 세면 되는 문제였다.

 

(코드는 아래와 같다.-python)

def factorial(n):           # 팩토리얼을 구하는 재귀함수 
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return factorial(n-1)*n


def findzero(n):            # 숫자 맨 뒤에 0이 몇개 있는지 출력하는 함수 
    cnt = 0
    string_number = str(n)
    reverse_number = string_number[::-1]
    for s in reverse_number:
        if s != '0':
            break
        else:
            cnt += 1
    print(cnt)


n = int(input()) 
findzero(factorial(n))

string[::-1] 같이 문자열을 거꾸로 뒤집어 주는 방법 또한 배웠다.

문제는 쉽게 통과되었지만, 

생각해봐야 할 것이 있었다.

 

1. 반복문이나 재귀함수로만 팩토리얼을 구현해봤는데, 동적 계획법(메모이제이션)을 통해서도 팩토리얼 함수를 구현해봄으로써 이에 대해서 배워봐야 겠다,,,

 

2. 이 문제가 '정수론 및 조합론' 에 속한 이유가 무엇일까?
        ---- 소인수분해의 성질을 활용하여 N!의 끝에 0이 얼마나 많이 오는지 구하는 문제 라는데,,,

---

 

먼저, 1번 물음에 대해 공부하기 전,

구글링을 통해 재귀함수의 문제점 및 해결책을 살펴보았다.

 

※ 재귀함수의 문제점 및 해결책

 

※ 재귀함수의 문제점 및 해결책을 알아보자.

재귀함수의 가장 큰 문제점은 효율성이 좋지 못하다는 점인데,
이미 계산되었던 값일지라도 의미없이 다시 계산을 반복하기 때문이다.
실제로 재귀함수로 팩토리얼을 구하는 방법과
for문으로 팩토리얼을 구하는 방법의 시간차이가 2.4배 정도 발생한다.
(피보나치 수열은 더욱 차이가 심각하다.)

위와 같은 문제점을 해결하기 위해 동적계획법(Dynaminc Programming, DP)에서
활용되는 메모이제이션(Memoization)을 사용해야 한다.
DP는 코딩테스트에서 너무나도 다양한 모습으로 등장하기 마련이다.
핵심적인 내용만 얘기하자면,
DP에서는 큰 문제를 해결하기 위해 작은 문제들을 해결해나가야 하는데, 그 작은 문제들의
결과값은 변하지 않아야 한다. 그리고 그 결과값이 변하지 않는 작은 문제들이 자꾸
반복해서 일어나게 된다. 메모이제이션은 자꾸만 반복되지만 

그 결과값은 변하지 않는 작은 문제들의 결과값을 저장하는 것을 의미한다.

쉽게 말해, 메모이제이션을 통해 이미 결과값이 기록되는 특정 문제가 반복할 때,
불필요한 계산은 패스하고 기록되어 있는 값만 불러오면 아주 빠르게 해결할 수 있다.
재귀함수 또한 큰 문제를 해결하기 위해 탈출 조건을 만날 때까지 작은 문제들을 풀어나가야 하고,
그 과정 중에 반복되는 작은 문제들이 있을 수 있다.

(메모제이션을 이용한 팩토리얼 코드는 아래와 같다)

# n이 0과 1일 때의 팩토리얼 값을 미리 dictionary에 저장해두었다.
dictionary_facto = {0: 1, 1: 1}

def factorial(n):
    if n in dictionary_facto:
        return dictionary_facto[n]   # 값이 저장되어 있으면, 그대로 그 값을 출력

    dictionary_facto[n] = factorial(n-1)*n
    return dictionary_facto[n]

이처럼, 재귀함수의 효율성이 많이 떨어지게 될 경우, 재귀함수가 한번 호출될 때마다의 결과값을
저장하여 효율성을 증대시켜보자. -> 동적계획법

---

2번 물음에 대해 공부하기 전, 규칙을 찾아보자.

소인수분해의 성질을 활용하여 N!의 끝에 0이 얼마나 많이 오는지 구하는 문제라고 했으므로

규칙이 있을 것이다.

구글링을 해봤더니, 규칙은 이러했다.

 

팩토리얼로 얻을 수 있는 수를 인수 분해 했을때, 0이 늘어나는 순간은 10(2x5)가 곱해지는 순간이다.

2의 갯수는 짝수마다 나와서 5보다는 많다. 따라서 5의 개수를 찾으면 쉽다.

예를 들어, 10!이면 5에서 한번, 10에서 한번 --> 그래서 답이 2

( 10 ! = 3628800 ) 

원래는 for-loop를 활용해서 조건식은 5를 계속 곱해주고, for-loop 안에서는 5로 나눠주어 5의 갯수를 찾아야 한다.

하지만 문제에서 주어진 N의 범위(0<N<500)가 크지 않으니 그냥 print 문으로 해결해도 된다.

 

5와 10에서만 0이 늘어날 텐데, 10도 5의 배수이니 5로 나눴을 때 몫만큼 0이 존재하는 것 아닐까 ? 라고 생각할 수도 있는데 그렇지 않다.

>>> print(N//5)   # 틀렸다!

25! 에서는 뒤에 있는 0의 개수가 5개가 아닌 6개가 존재했다.

그렇다는건 25가 5를 두 번 곱한 값이니까 5의 제곱의 배수에서는 2씩 늘어나고 5의 세제곱의 배수에서는 3씩 늘어날 것이라는 것을 예상할 수 있다. 그럼 25로 나눈 몫도 추가로 더해주고 125로 나눈 몫도 추가로 더해주면 된다!

 

125도 넣어줘야하는 이유는 N의 범위가 125를 포함하기 때문이다. 또, 5를 3번 포함하기 때문.

(10은 2와 5의 곱이며 팩토리얼에 2는 충분히 많기때문에 5가 나올때마다 1씩 더해주면 된다. 여기서 주의할점은 5^n인 수일때는 n개만큼 더해주어야 한다. ) (625는 500 범위 밖이니 제외.)

 

 

(코드는 아래와 같이 매우 간단하다. 단 2줄이다.)

N = int(input())
print(N//5 + N//25 + N//125)

---