[BaeKJoon] 2004번: 조합 0의 개수 (Python)

1일 최소 1문제 4일차!

오늘의 문제는 조합 속의 0의 개수를 구하는 문제입니다.

2004번: 조합 0의 개수

왼쪽 nCk                         /                                     오른쪽 10C7

먼저 nCk일 경우 왼쪽과 같이 연산을 실시합니다.

여기서 n이 10 k가 7일 경우 10!을 3!과 7!로 나누어 계산합니다.

 

이를 인지하고 이전에 풀었던 팩토리얼 문제를 활용하여 풀어보려합니다.

[BaeKJoon] 10872번: 팩토리얼 (Python)

def factorialNum(N):
    if N == 0 or N == 1:
        return 1
    else:
        fact = 1
        for i in range(1, N + 1):
            fact = fact * i
    return fact

def factorialTopNum(N, M):
    top = 1
    for i in range(N-M+1, N+1):
        top = top * i
    return top


N, M = map(int, input().split())

combination = int(factorialTopNum(N, M) / factorialNum(M))

print(combination)

comb_list = list(str(combination))

comb_list_len = len(comb_list)

count = 0

for i in range(len(comb_list)):
    if comb_list[comb_list_len-1-i] !='0':
        break
    elif comb_list[comb_list_len-1-i] == '0':
        count = count + 1
print(count)

결과는!

m과 n으로 들어오는 숫자가 (0≤m≤n≤2,000,000,000, n!=0) 이므로
엄청나게 큰 숫자가 들어오게 되면 시간초과가 발생하는 것 같습니다.

 

이문제는 조합을 구해서 답을 내는 것이아닌 조합 내의 0의 개수를 구하는 문제이므로

이번에는 나눗셈은 지수의 차의 개념과

팩토리얼 내의 0을 만들 수 있는 2와 5의 개수를 가지고 풀어보았습니다.

사진 출처 : ZUM 학습백과 - 지수의 차

M과 N을 입력받았을떄 M! 을 N!과 (M-N)!로 나눈 값이 조합입니다.

 

그럼 여기서 0의 개수를 구하는 것은

0의개수

=

M!가 가지고 있는 2의 개수 - N!이 가지고 있는 2의 개수 - (M-N)!이 가지고 있는 2의 개수

/

M!가 가지고 있는 5의 개수 - N!이 가지고 있는 5의 개수 - (M-N)!이 가지고 있는 5의 개수

중에 작은 수

 

가 됩니다.

 

이것을 코드로 구현하면

def countNum(N, num):
    count = 0
    divNum = num
    while( N >= divNum):
        count = count + (N // divNum)
        divNum = divNum * num
    return count

M, N = map(int, input().split())

print(min(countNum(M, 5) - countNum(N, 5) - countNum(M-N, 5), countNum(M, 2) - countNum(N, 2) - countNum(M-N, 2)))

생각을 바꾸니 해결할 수 있었습니다.

 

SOMJANG/CODINGTEST_PRACTICE