0의 개수

괜찮은 아이디어가 하나 있다.

 

#1676번 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

입력된 수의 팩토리얼을 구하고, 뒤에서부터 0이 아닌 수가 나올 때 까지 0의 개수를 구하는 문제이다.

어떻게 보면 비교적 순진하게 풀었다.

#1676번 #파이썬

num = int(input())

if num == 0:
    print(0)

else:

    for i in range(2, num):
        num *= i

    loop = str(num)
    answer = 0
    for s in range(len(loop)-1, -1, -1):
        if loop[s] != "0":
            break
        else:
            answer += 1

    print(answer)

그냥 팩토리얼 구하고, 스트링 역전시켜서 0 개수 구하기..

정말 순진한 코드

 

그리고 나서

#2004번 조합 0의 개수 https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

를 풀기 시작했는데, 전혀 감이 잡히지 않았다. 검색 끝에 1676번과 비슷한 방법으로 풀면 된다는 사실을 알게 됐는데 왠걸 뭔 개소린지...

 

알고보니 내가 1676번도 효율이 떨어지는 방법으로 풀었던 것이었다.

맨 뒤(1의 자리)부터 0의 개수라는건 결국 그 수를 구성하는 인수 중 10의 개수를 묻는 것이었다.

죽 2*5의 개수를 세어주면 된다.

 

2004번에서 조합을 구할 때에는 총 팩토리얼 함수를 3번 사용해야 하는데, 수가 커질수록 시간은 엄청나게 소모된다. 당연히 팩토리얼을 다 구하고 있으면 시간초과가 난다.

n 팩토리얼 = n이하의 수의 곱 이니까,

n이하의 모든 수에서 2와 5의 개수를 구해주면 된다.

이 또한 신박한 방법이 있어서 정말 놀라웠다.

무슨 말인지 이해가 됐으면 좋겠다.

 

10! = 10 9 8 7 6 5 4 3 2 1 의 곱인데,

1) 이 중 2를 가지고 있는 수는 총 5개이다. 10을 2로 나눴을 때의 정수값과 같다.

2) 다음으로 4(2의 2제곱)을 가지고 있는 수는 총 2개이다. 이는 1)에서 나온 정수값(개수)를 다시 2로 나눴을 때의 정수값과 같다.

3) 다음으로 8(2의 3제곱)을 가지고 있는 수는 총 1개이다. 이는 2)에서 나온 정수값(개수)를 다시 2로 나눴을 때의 정수값과 같다.

4) 3)의 정수값을 다시 2로 나누면 0이다. 즉 더 이상의 2는 없다.

 

결론) 10팩토리얼에는 2가 8개 들어있다.

 

이걸 뭐라고 표현해야 할지 모르겠지만, 이 이론은 모든 수에 동일하게 적용된다.

코드로 표현하면 다음과 같다.

def count_num_of_factorial(num, n):
    count = 0
    while num != 0:
        num //= n
        count += num
    return count

num팩토리얼의 인자 중 에서 n의 개수를 구하는 함수라고 보면 된다.

 

이 방식을 2004번 조합의 개수에 적용하면

#2004번 #파이썬

num1, num2 = map(int, input().split())
nums = [num1, num2, num1-num2]


def count_five(num):
    count = 0
    while num != 0:
        num //= 5
        count += num
    return count


def count_two(num):
    count = 0
    while num != 0:
        num //= 2
        count += num
    return count


two = [count_two(x) for x in nums]
five = [count_five(x) for x in nums]
two = two[0] - two[1] - two[2]
five = five[0] - five[1] - five[2]

print(min(two, five))

이 된다.

조합의 경우에는 nCm = n! / m! * (n-m)! (n>m) 이니까 각각의 수 (n, m, n-m)에서 2와 5의 개수를 구해준다.

n팩토리얼을 나머지 두 수로 나누는 구조이기 때문에 지수계산 상에서는 뺄셈이 된다.

따라서 n!의 2와 5의 개수에서 나머지 두 수의 2와 5의 개수를 빼주면 된다.

 

10이 되기 위해서는 2와 5의 개수가 동일해야 함으로 2와 5의 개수중 작은 값이 10의 개수 즉 1의자리 부터 0의 개수가 된다.

 

완성.

 

이 이론을 1676번 문제에도 적용을 시켜보자

 

#1676번 파이썬

num = int(input())

count = 0
while num != 0:
    num //= 5
    count += num
print(count)

개쉽다.

 

의문이 들 수 있다. 왜 1676에서는 5의 개수만 세어줬냐고.. 보통의 팩토리얼에서는 2의 개수가 5보다 많다. 즉 항상 5의 개수가 더 작기 때문에 5만 세어줘도 정답이 된다. 다만 2004번에서는 지수상에서의 뺄셈이 존재하기 때문에 위 사실을 확신할 수 없어서 min함수 연산을 추가해준 것이다.

 

 

휴 오늘도 힘들었다.