2004 python 조합 0의 개수

조합은 파이썬에서 라이브러리를 제공해주는 것으로 알고 있다.

 

import math

# nCr 계산
n = 5
r = 3
result = math.comb(n,r)

 

Q1.숫자를 list()로 감싸는 것은 에러가 나는가?

O. 에러가 난다. 주의할 것.

 

따라서 문제에 대한 답 코드는 다음과 같이 작성하였다.

import math, sys

def input():
    return sys.stdin.readline().rstrip()

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

result = math.comb(n,m)
result_list=list(str(result))
cnt=0

for i in reversed(result_list):
    if i=='0':
        cnt+=1
    else:
        break
print(cnt)

 

하지만 리스트 연산이 많아서 그런지 시간 초과가 떴다.

import math, sys

def input():
    return sys.stdin.readline().rstrip()

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

result = math.comb(n,m)
cnt=0

for i in str(result)[::-1]:
    if i=='0':
        cnt+=1
    else:
        break
print(cnt)

 

흠.. 이렇게 했는데도 시간 초과가 뜬다. 그러면 어떻게 하지?

 

일단 개선 방안을 생각해보았을 때, math.comb(n,m) 이 함수가 생각보다 시간이 오래걸리는 듯하다.

직접 만들어서 쓰는게 훨씬 효과적일 듯 하다.

 

일단 팩토리얼 함수 만들어보자.

def factorial(num):
    result=1
    for i in range(2,num+1):
        result *=i
    return result

조합 식은 다음과 같은데, 

우선 조합을 코드로 표현해보겠다.

def combination(n,k):
    #예외 처리
    if k > n:
        return 0
    if k == 0 or k==n:
        return 1
    
    #팩토리얼 계산
    def factorial(num):
        result=1
        for i in range(2,num+1):
            result *=i
        return result
    
    #이때 조합의 계산은 항상 정수이기 때문에, 정수 계산을 위해서 /가 아니라 //를 사용한다.
    result = factorial(n)//(factorial(n-k)*factorial(k))

    return result

 

이때 k!과 n-k!에서 중복되는 부분이 상당히 생긴다.

이 부분을 한 번 메모이제이션으로 해결해보자.

 

열심히 아래와 같이 코드를 제작하였다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def comb(n,k):
    if k > n:
        return 0
    if k==0 or n==k:
        return 1
    
    #k가 n/2보다 큰 경우, nCk=nC(n-k)와 같음. 더 작은 수로 바꿔주는 과정
    if k > n/2 :
        k = n-k

    result=1
    for r in range(k): #r-1까지 돌 것임
        result = result * (n-r) // (r+1)

    return result

n, r = map(int, input().split())
print(comb(n, r))

 

하지만 여전히 에러가 났다 ^_^ 한 단계 더 가야하나보다.

파스칼의 삼각형을 이용하는 방법도 생각하였으나, 정답을 보니 0의 개수는 2와 5의 개수로 판단하는 것 같다.

 

팩토리얼에서 특정 소인수의 개수를 계산하는 방법

 

1.모든 2의 배수를 카운트한다.

: n을 2로 나눈 몫은 n 이하의 모든 수 중 2의 배수의 개수를 의미한다.

몫 = n이하의 2의 배수들의 개수

이게 잘 이해가 안됐었는데, 나열해놓고 세어보면 결국 그렇다. 그냥 외우자.

예를 들어, n=10이면 10//2=5로, 2 4 6 8 10 총 5개의 숫자가 하나 이상의 2를 갖고 있다.

 

이때 코드는 두 가지 관점에서 짤 수 있다. 결국 결과는 같다.

1) 나누는 수를 2, 4, 8 ...로 높인다.

2) 주어진 n을 2로 나눠가면서 반복 계산한다.

 

원리를 이해하기에는 1번이 더 쉽지만 코드 짜기에는 2번이 더 쉬운 듯 하다.

드디어 정답 코드

 

import sys

def input():
    return sys.stdin.readline().rstrip()

def cnt(s,n):
    if n < s:
        return 0
    cnt=0
    while n>=s:
        cnt +=n//s
        n=n//s
    return cnt

n,m = map(int,input().split())
two_cnt = cnt(2,n) - cnt(2,n-m) - cnt(2,m)
five_cnt = cnt(5,n) - cnt(5,n-m) - cnt(5,m)

print(min(two_cnt,five_cnt))

 

 

+) sys.stdin.readline()과 sys.stdin.read()의 차이

이때 sys.stdin.readline()과 sys.stdin.read()의 차이가 궁금해서 찾아봤다.

-read()

: 여러 줄 입력을 처리할 때 사용된다. 따라서 메모리 사용량이 많아질 수 있으나, 빠르게 많은 양의 데이터 읽기 가능하다.

 

-readline()

: 한 줄씩 입력을 처리한다. 따라서 메모리 사용량이 상대적으로 적으나, read()보다 느리다.