[백준] 2004 조합 0의 개수 (Python)

2004번: 조합 0의 개수

---

문제 풀이

 

최근 풀었던 문제 중에 가장 아이디어를 떠올리기 어려웠던 것 같다.

 

기본적으로 알아야 할 조합의 개념은 nCr = 1/r! * n!/(n-r)! 이라는 점이다.

 

입력의 개수는 두 개로 정해져 있지만, 수의 범위가 20억까지도 될 수 있으므로 단순하게 조합을 직접 계산하면 시간초과가 날 수밖에 없다.

 

하지만 문제에서 요구하는 것이 조합의 결과를 나타내라 - 가 아닌

조합의 결과에서 끝자리 0의 개수를 나타내라 - 이므로

10이 몇번이나 곱해졌는가에 초점을 맞춰야 한다.

 

10은 2와 5의 곱으로 나타낼 수 있으므로, 조합의 결과를 인수분해 했을 때 2의 지수승과 5의 지수승을 비교하여 더 작은 것을 출력하면 된다.

작은쪽을 따라가게 된다.

 

하지만 이 또한 결국 조합의 결과를 알고 있어야 하는 것이라는 점에서 문제를 해결하지는 못하는데,

여기서 기발한 아이디어가 필요하다.

 

팩토리얼은 1부터 n까지 모든 수를 곱한다.

팩토리얼의 결과를 알고 있지 않아도 어떤 수 x가 몇번 곱해졌는지 알 수 있다.

 

20! 에서 2가 몇번 곱해졌는지를 구하고 싶다면,

20 // 2 를 하게 되면 10이 나오는데, 이는 20까지의 수 중 2의 배수 개수와 동일하다.

20 // 2**2 를 하게 되면 5가 나오는데, 이는 20까지의 수 중 2**2 즉, 4의 배수 개수와 동일하다.

 

이러한 과정을 계속 반복하게 되면 우리가 원하는 2의 지수승 개수를 알 수 있게 된다.

 

여기까지 읽었을 때 이해가 잘 되지 않는다면 다음 그림을 함께 보도록 하자.

 

이 개념은 2 뿐만 아니라 5, 7, 등등 다른 모든 수에도 대입이 가능하다.

 

이 아이디어를 이해했다면 더 이상 문제점은 없을 것이다.

 

 

---

 

코드

 

def counter(num, n):
    cnt = 0
    while num:
        num //= n
        cnt += num
    return cnt


n, m = map(int, input().split())
cnt_2 = counter(n, 2) - counter(m, 2) - counter(n-m, 2)
cnt_5 = counter(n, 5) - counter(m, 5) - counter(n-m, 5)
print(min(cnt_2, cnt_5))

---

이해가 안되는 부분이 남아있다면 댓글 남겨 주세요.