[백준/파이썬/수학] 2004번 조합 0의 개수 코딩테스트 연습풀이 실버2

문제 출처: https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

 

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

 

예제 입력 1

25 12

 

예제 출력 1

2

 

시간초과가 나온 코드

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

n_2 = 0
n_5 = 0

for i in range(1, n):
    if i == m+1:
        print(min(n_2,n_5))
        break
    while True:
        tmp = n-i+1
        if tmp/2 == tmp//2:
            while True:
                tmp = tmp//2
                n_2 += 1
                if tmp % 2 != 0:
                    break
        if tmp/5 == tmp//5:
          while True:
                tmp = tmp//5
                n_5 += 1
                if tmp % 5 != 0:
                    break
        break
    while True:
        tmp = i
        if tmp/2 == tmp//2:
            while True:
                tmp = tmp//2
                n_2 -= 1
                if tmp % 2 != 0:
                    break
        if tmp/5 == tmp//5:
          while True:
                tmp = tmp//5
                n_5 -= 1
                if tmp % 5 != 0:
                    break
        break

답은 나오지만 시간초과! 구글링을 조금 한 후 코드를 변경하였습니다

 

정답

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

def combi(n, k):
    cnt = 0
    while n:
        n //= k
        cnt += n
    return cnt

n_2 = combi(n, 2) - combi(m, 2) - combi(n - m, 2)
n_5 = combi(n, 5) - combi(m, 5) - combi(n - m, 5)

print(min(n_2, n_5))

수학을 풀때 combination이 생각나서 함수이름을 combi라고 지었습니다

위의있는 코드와 다른점은 불필요하게 시간을 잡아먹는 요소들을 제거했다는 점인 것 같습니다

답은 똑같이 나와요