[백준] 2004번 (python 파이썬)

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

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

def get_count(n, k):
  count = 0
  while n:
    n = n // k
    count += n
  return count

result = min(get_count(n, 2) - get_count(n-m, 2) - get_count(m, 2),\
             get_count(n, 5) - get_count(n-m, 5) - get_count(m, 5))
print(result)

 

n! 에서 끝자리 0의 개수를 구하는 문제이다.

당연히 1 × 2 × 3 × ... (n-1) × n 을 하고 그 결과값에서 끝부분의 0의 개수를 구해도 된다.

단, n의 입력값이 작은 경우에만 된다.

입력값의 미친 범위를 보아라. 20억이다. 

시간제한이 2초임에도 불구하고 단순 반복만 하더라도 시간초과가 날 것이다.

팩토리얼 값을 구하려면 비트코인 체굴장 그래픽 카드를 들고 와야 하지않을까?

 

그래서 생각했다.

뒤에 0이 나온단 건 10이 만들어 진것이고  2와 5가 1개씩 있다는 얘기잖아?

여기까지 생각했다.

n팩토리얼에 2와 5가 몇 개씩 들어있는지 구하면 된다.

그 중 작은 개수를 구하면 된다. (2가 3개, 5개 1개이면 1이 답)

1에서 2와 5의 개수를 구하고

2에서 2와 5의 개수를 구하고

3에서 2와 5의 개수를 구하고

4에서 2와 5의 개수를 구하고

...

n에서 2와 5의 개수를 구한다.

 

근데 이러면 20억번을 또 반복 해야한다.

이 방법이 아니다.

 

솔루션을 봤다.

2와 5의 개수를 구한다는 방향까진 맞았는데 구하는 방식이 나와는 관점 자체가 달랐다.

 

예를들어, 10 팩토리얼의 2의 개수를 구한다고 했을때 나는 아래 코드처럼 생각했다.

count = 0
for i in range(1, 11):
  n = i
  while not(n % 2):
    count += 1
    n = n // 2
else:
  print(count)

1부터 10까지 반복하면서 2로 나누고 나눠질때마다 카운트 하는것이다.

하지만 솔루션에서는 접근이 나와 달랐다.

n = 10
count = 0
while n:
  n = n // 2
  count += n
print(count)

처음엔 도저히 이해가 안되었다. 

 

다음과 같이 이해해보자.

10 팩토리얼은 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 의 곱으로 구성되어 있다.

여기서 2가 들어있는 건

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => 2가 총 5번 들어있다.

여기서 4가 들어있는 건

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => 4가 총 2번 들어있다.

여기서 8이 들어있는 건

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => 8이 총 1번 들어있다.

 

4는 2가 2개이고, 8은 2가 3개이다.

즉, 2가 있는 개수 + 4가 있는 개수 + 8이 있는 개수 = 총 2가 들어간 횟수이다.

10을 2로 나눈 몫이 2가 들어있는 개수이고

10을 4로 나눈 몫이 4가 들어있는 개수이고

10을 8로 나눈 몫이 8이 들어있는 개수이다.

 

솔루션은 이런 관점으로 이 문제에 접근하였다.