[Python] 백준 #2004- 조합 0의 개수

문제

---

2004번: 조합 0의 개수

코드

---

My answer-(Wrong_answer)

def counts(n,a):
    cnt=0
    if(n<5):
        return 0
    if(n%a!=0):
        n=n//5*5
    while(1):
        if(n%5==0):
            cnt+=n//a
            n//=a
        else:
            break
    return cnt

import sys

a,b=map(int,sys.stdin.readline().split())
min5=counts(a,5)-counts(a-b,5)-counts(b,5)
min2=counts(a,2)-counts(a-b,2)-counts(b,2)
if(min(min5,min2)<0):
    print(0)
else:
    print(min(min5,min2))

Another answer

def counts(i, j):
    count = 0
    while i:
        i //= j
        count += i
    return count

import sys

a,b=map(int,sys.stdin.readline().split())
min5=counts(a,5)-counts(a-b,5)-counts(b,5)
min2=counts(a,2)-counts(a-b,2)-counts(b,2)
if(min(min5,min2)<0):
    print(0)
else:
    print(min(min5,min2))
----------------------------------------------
f=lambda n,d:n//d+f(n//d,d)if n else 0
a,b=map(int,input().split())
print(min(f(a,i)-f(b,i)-f(a-b,i)for i in[2,5]))

 

풀이

---

우선 기본적인 풀이방법은 직접 조합을 구해서 하는 방법이 있긴한데, 아래 식처럼 팩토리얼이 3번이나 들어간다.

팩토리얼을 쓰는순간 입력값이 커질수록 실행시간이 매우 오래걸리므로 팩토리얼을 안쓰고 구하는 법을 생각해봤다.

이전 문제에 팩토리얼 0의 개수때 한 것처럼 0의 갯수만 세면 되기때문에 각각의 팩토리얼의 0의 갯수를 세주었다. 우선 세 숫자를 a,b,c라할 때 각각의 수에서 5의 개수를 구해준다. 이후에 각 수의 2의개수를 구해준다음 최종 5,2의 개수에서 최솟값을 선택해줘야 10의 갯수가 나온다. 내 코드는 틀렸었는데 우선 코드는 거의 비슷했는데 2와 5의개수를 구하는 함수를 잘못짰다. 나는 예를들어 7이나 3같이 5나 2로 안떨어지는 수가 들어오면 이걸 그 수보다 작은 5나 2의 배수로 만들어주려고 이상한 조건문을 추가했는데 걍 몫으로 계산하면 필요없는 부분이었다. 아무튼 위에서 말한걸 다시 예를 들어서 설명하자면 우선 입력갑이 25와 12면 (25! / 12! / 13!) 에 있는 10의 개수를 구하면 되는것이다. 우선 25에서 5의 개수를 구하면 6개, 12!에서는 2개, 13!에서도 2개이다. 식이 나누기이므로 약분을 하면 갯수를 뺴주면 되므로 총 계산식에서의 5의개수는 6-2-2는 2개이다. 다음으로 25!에서 2의 개수는 22개, 12!에서는 10개, 13!에서는 10개이므로 총 2개이다. 10이 만들어지려면 2하나와 5하나가 필요하므로 총 개수중 min(2의총개수,5의총개수)를해주면 총 10의 개수를 구할 수 이따. 따라서 min(2,2)는 2가 나온다. 이해가 안가는 부분은 댓글로 물어봐주시면 감사하겠습니당.

+ 마지막 코드는 내가 설명한 코드를 lambda식과 더 간단하게 표현한 것이다.