조합 0의 개수
[BOJ] 2004 조합 0의 개수 (Python / 파이썬)
[BOJ] 2004 조합 0의 개수 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/2004 조합 nCm의 끝자리 0의 개수를 출력하는 문제이다. 🛠 풀이 이 문제는 시간초과를 신경써야 하는 문제이다. Step 1. 이 문제를 단순히 nCr = n! / r!(n-r)!을 계산한 후에 10으로 나눠서 계산하면 문제에서 주어진 입력의 범위때문에 시간초과가 난다. Step 2. 그렇다면 끝자리가 0이 나올 수 있는 경우를 생각해본다. 끝자리가 0이 되려면 2와 5의 곱으로 이루어져야한다. 즉, 2와 5의 쌍의 갯수를 구하면 끝자리 0의 개수를 구할 수 있다. Step 3. 다시 한번, 10이 만들어지려면 2와 5가 쌍을 이뤄야 하므로 2의 갯수와 5의 갯수 중 더 작은 것을 선택하면 된다. 🖊 나의 코드 import sys i..