2004 : 조합 0의 개수
어떤 문제인가?
1676번 문제의 심화 유형. 뒤에 있는 0의 개수를 세는 문제.
수가 너무 크다
Wolfram alpha로 를 계산하면 자그마치 10의 지수가 10만에 달한다. 정공법으로 풀면 파이썬조차 메모리 초과로 나가떨어진다.
1676번 문제에서 으로 나눈 값을 더했다. 이 문제도 원리는 동일하다. 나 또한 유사하게 접근해서 풀었다.
내 코드
import math
k1, k2 = 0, 0
n, m = map(int, input().split())
for i in range(int(math.log(n,2)),0,-1):
k1 = k1 + int(n/2**i)
if m>0:
for i in range(int(math.log(m,2)),0,-1):
k1 = k1 - int(m/2**i)
if n-m > 0:
for i in range(int(math.log(n-m,2)),0,-1):
k1 = k1 - int((n-m)/2**i)
for j in range(int(math.log(n,5)),0,-1):
k2 = k2 + int(n/5**j)
if m>0:
for j in range(int(math.log(m,5)),0,-1):
k2 = k2 - int(m/5**j)
if n-m>0:
for j in range(int(math.log(n-m,5)),0,-1):
k2 = k2 - int((n-m)/5**j)
print(min(k1, k2))
import math
k1, k2 = 0, 0
n, m = map(int, input().split())
for i in range(int(math.log(n,2)),0,-1):
k1 = k1 + int(n/2**i)
if m>0:
for i in range(int(math.log(m,2)),0,-1):
k1 = k1 - int(m/2**i)
if n-m > 0:
for i in range(int(math.log(n-m,2)),0,-1):
k1 = k1 - int((n-m)/2**i)
for j in range(int(math.log(n,5)),0,-1):
k2 = k2 + int(n/5**j)
if m>0:
for j in range(int(math.log(m,5)),0,-1):
k2 = k2 - int(m/5**j)
if n-m>0:
for j in range(int(math.log(n-m,5)),0,-1):
k2 = k2 - int((n-m)/5**j)
print(min(k1, k2))
나는 최댓값을 먼저 결정한 후 이를 바탕으로 빼 나가는 방식으로 풀었다. 내가 다만 3번이나 틀렸던 것은 은 정의되어 있지 않음을 깜빡했던 점이다.
남들의 풀이
def count(n, r, d):
result, x = 0, d
while x <= n:
result += n//x - (n-r)//x - r//x
x *= d
return result
n, r = map(int, input().split())
print(min(count(n, r, d) for d in [2, 5]))
def count(n, r, d):
result, x = 0, d
while x <= n:
result += n//x - (n-r)//x - r//x
x *= d
return result
n, r = map(int, input().split())
print(min(count(n, r, d) for d in [2, 5]))
rapaeljin님의 풀이
-> https://www.acmicpc.net/source/15118501
나는 최댓값을 먼저 결정했지만, 간결한 풀이는 대부분 상향식으로 접근했다. 2, 5부터 시작해서 말이다. 내가 보기에도 이 방식이 가장 낫다.
Author And Source
이 문제에 관하여(2004 : 조합 0의 개수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qoo0302/2004-조합-0의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)