백준 2004 풀이 (조합 0의 개수)

진짜 개어려웠다.

처음에는 저번에 DP로 조합 푼거 생각나서 그러한 방식으로 풀면 되나 싶었는데 조건으로 나오는 값이 너무 컸다. DP로 풀어도 분명히 시간 초과날게 뻔했다.

값이 거의 뇌절 급으로 크다.

그래서 이것저것 뒤져봐도 안되서 DP로 풀었더니 아니나 다를까 시간초과가 났다. 그래서 고수들이 푼 방식을 슬쩍 훔쳐봤다.

슬쩍 봤더니 0이 나오기 위해서는 조합의 결과안에서 2와 5가 한쌍으로 나와야 끝자리에 0이 생성된다. 

따라서 해당 값의 결과에 2와 5의 개수가 몇개나 나오는지 확인해야한다.

처음에는 고수의 코드를 보고도 이해가 안갔다. 5!에 2와 5가 몇개 있는지 보려면 5!을 구하고서 2나 5로 나누면 되는거 아닌가? 라는 생각도 했다.

그런데 고수들은 5를 2로 나눠서 구하거나 5를 5로 나눠서 구하고 있었다.....

 

그래서 곰곰히 생각해보았다.

예를 들어 5!은 5, 4, 3, 2, 1을 곱해서 구해야한다.

그럼 5까지 수중에 2의 배수를 찾는다. 그 이유는 2의 배수에 2가 들어있기 때문이다.

5, 4, 3, 2, 1 에서 4와 2가 2의 배수로 총 2개가 들어있다.

그럼 2를 가진 값들을 2로 나눈다. 그럼

2, 1 로 2가 1개 들어있다.

그럼 2를 가진 값들을 2로 나눈다. 그럼

1 로 총 0개가 들어있다.

그럼 결과적으로 2개, 1개, 0개 이므로 5! 안에는 2가 3승 만큼 들어있다라고 할 수 있다.

따라서 5를 2로 나누며 0까지 나올때 나오는 몫의 값이 2의 개수라고 할 수 있다.

아주 겁나게 어렵다. 솔직히 이해가 안되서 유목민처럼 구글링하며 풀이를 찾아다녔다.

 

이러한 풀이를 이용하여 코딩을 하면 코드는 상당히 간단해진다.

n,m = map(int,input().split())

def check(n, number):
    count = 0
    while n != 0:
        n = n // number
        count = count + n
    return count
print(min(check(n,2)-check(m,2)-check(n-m,2),check(n,5)-check(m,5)-check(n-m,5)))

혹시나 이 글을 읽는 분은 다른 풀이를 꼭 참고하기 바란다. 나도 이거 이해를 100% 하지 못했다.