nayounsang1   2년 전

조합연산을 제 함수보다 더 빠르게 할 수 있나요?

주석친 것도 시간초과가 뜨네요

팩토리얼구하면서 곱해지는 5와 2가 몇개있는지는 딱봐도 넘 오래걸릴거같네요 

bd2646   2년 전

일단 조합연산 자체도 이런식으로 for문을 두개 쓰지않고 하나만 사용해서 해결할 수 있습니다.

n, m=map(int,input().split())
count=1
m=min(n-m,m)
for i in range(m):count*=(n-i)/(i+1)

그렇지만 실제로 실행해보진 않았는데 아마 이쪽도 시간초과는 날것같네요.

/// 

이 문제에서 연산시간을 줄이는 방법은

A 와 B라는 숫자가 들어왔을때, A와 B를 그냥 조합연산을 해서 뒤에 오는 0의 개수를 세는 것 이 아니라

A와 B의 조합연산시 

분자쪽에 들어가게 될  2,5 Set의 합  - 분모쪽에 들어가게될 2,5 Set의 합을 빼주는 방법을 사용하는 것입니다.

nayounsang1   2년 전

bd님 혹시 왜 더 빠른지 설명가능할까요?

제 생각은 

후자로하면 조합구하는 반복문에서 각 곱하는 숫자를 2와 5을 나누어 그 개수를 세므로 시간이 더 오래걸릴것 같은데

결과값을 구하고 그 뒤에 0을 세는 법은 반복문이 아니라 단순연산이므로 시간이 더 적을것 같아서요

bd2646   2년 전

23개중 10개를 선택하는 경우를 예로 들겠습니다.

이 경우, (23*22*21....14)/(10/9/8..../2/1) 입니다.

이 식의 0의 자리수를 계산하기 위해 23~14, 10~1까지를 전부 계산하지 않아도 괜찮습니다.


제가 쓴 방법보다 좋은 방법이 많겠지만,

우선 제가 쓴 방법으로 설명을 드리자면

위 식은 이렇게 간략화 할 수 있습니다.

23! / (13! * 10!)

이 식의 분자의 0의 개수가 n개이고,

분모의 0의 개수가 m개라면, 

이 식의 0의 개수는 n-m개일 것입니다.

그래서 0의 개수를 구해보자면,

 13팩토리얼 같은 경우에는 1~13까지 곱해지므로

2,4,6,8,10,12 와  5,10가 곱해질테고

2,5 set가 두개 나오므로 뒤에 0이 두개 붙을겁니다.


위 식을 이에따라 계산하면

23! =  4

13! = 2

10! = 2

이므로 4-2-2가 되어, 23개중 10개를 선택하는 경우에 뒤에 오는 0의 개수는 0인것을 알 수 있습니다.









댓글을 작성하려면 로그인해야 합니다.