https://www.acmicpc.net/problem/2407
조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수 : =
의 분자를 그대로 곱해서 계산하면 메모리 초과가 예상된다.
따라서 최대한 메모리를 아껴서 해결할 수 있는 방법을 생각해본다.
n-m이 m보다 작은 경우 로 바꾼다.
ex). => 로 바꾼다.
if n-m < m: # nCm에서 m이 n의 절반보다 클 경우 n-m으로 바꾼다. m = n-m
분자, 분모를 리스트에 하나씩 담는다.
up_lst = [n-i for i in range(m)] # 분자를 리스트에 하나씩 담는다. down_lst = [i for i in range(1, m+1)] # 분모를 리스트에 담는다.
m이하의 소수를 재귀함수로 찾는다. 그리고 list에 담는다.
sosu_lst = [] # m이하의 소수를 찾아 담는다. def sosu(num): # num이하의 소수를 찾는 함수 if num > m: # 숫자가 m보다 큰 값이 나오면 안 찾는다. return for i in range(2, num): if num % i == 0: break else: sosu_lst.append(num) return sosu(num+1) sosu(2)
조합 중 분모를 소수의 곱 형태로 바꾼다.
ex).
분모를 소수의 곱으로 나타내기 위해 m+1 길이의 list를 만들고 각 인덱스를 숫자로 연결시켜 소수의 갯수(지수 값)만큼 넣어준다. 0과 1은 필요없으니 안 넣는다.
재귀함수를 이용한다. 2부터 m까지의 수 중 소수로 나누어 1이 될 때까지 나눈다. 소수로 나누어지면 그 때 인덱스 값을 올려 소수의 갯수를 넣어준다.
ex)
4*3*2*1
=> lst = [0,0,3,1,0] 소수인 2와 3에 지수 값을 넣어준다.sosu_cnt_lst = [0 for _ in range(m+1)] # 인덱스 맞춰 0~m까지의 소수 개수 초기화 def sosu_cnt(num): # 소수의 개수를 찾아주는 함수 if num > m: # 숫자가 m보다 큰 값이 나오면 안 찾는다. return new_num = num for sosu in sosu_lst: if new_num == 1: break while new_num % sosu == 0: # 위에서 구한 소수로 나누어 개수를 찾는다. new_num = new_num//sosu sosu_cnt_lst[sosu] += 1 return sosu_cnt(num+1) sosu_cnt(2)
분자를 분모로 나누어준다.
소수의 곱으로 이루어진 분모 리스트 중 소수가 작은 수부터 하나씩 분자를 나누어준다.분자의 숫자들을 담은 리스트도 하나씩 순회해가며 분모에서 픽한 소수의 개수가 0이 될 때까지 다 나누어준다.
다 나누고 남은 분자의 숫자들을 곱해 답을 구한다.
result = 1 for i in range(2, m+1): # 분모의 소수를 순서대로 가져와서 분자와 나누어 준다. if sosu_cnt_lst[i] != 0: # 소수이고 나눌 수 있는 횟수가 있으면 반복문으로 들어온다. for j in range(len(up_lst)): while (sosu_cnt_lst[i] != 0) and (up_lst[j] % i == 0): # 나누어지는지, 나눌 수 있는 수가 있는지 확인 up_lst[j] = up_lst[j] // i sosu_cnt_lst[i] -= 1 for num in up_lst: # 다 나눈 수를 곱한다. result *= num print(result)
n , m = map(int, input().split()) # nCm의 입력 n과 m
if n-m < m: # nCm에서 m이 n의 절반보다 클 경우 n-m으로 바꾼다.
m = n-m
up_lst = [n-i for i in range(m)] # 분자를 리스트에 하나씩 담는다.
down_lst = [i for i in range(1, m+1)] # 분모를 리스트에 담는다.
sosu_lst = [] # m이하의 소수를 찾아 담는다.
sosu_cnt_lst = [0 for _ in range(m+1)] # 인덱스 맞춰 0~m까지의 소수 개수 초기화
result = 1
def sosu(num): # num이하의 소수를 찾는 함수
if num > m: # 숫자가 m보다 큰 값이 나오면 안 찾는다.
return
for i in range(2, num):
if num % i == 0:
break
else: sosu_lst.append(num)
return sosu(num+1)
def sosu_cnt(num): # 소수의 개수를 찾아주는 함수
if num > m: # 숫자가 m보다 큰 값이 나오면 안 찾는다.
return
new_num = num
for sosu in sosu_lst:
if new_num == 1:
break
while new_num % sosu == 0: # 위에서 구한 소수로 나누어 개수를 찾는다.
new_num = new_num//sosu
sosu_cnt_lst[sosu] += 1
return sosu_cnt(num+1)
sosu(2)
sosu_cnt(2)
for i in range(2, m+1): # 분모의 소수를 순서대로 가져와서 분자와 나누어 준다.
if sosu_cnt_lst[i] != 0: # 소수이고 나눌 수 있는 횟수가 있으면 반복문으로 들어온다.
for j in range(len(up_lst)):
while (sosu_cnt_lst[i] != 0) and (up_lst[j] % i == 0): # 나누어지는지, 나눌 수 있는 수가 있는지 확인
up_lst[j] = up_lst[j] // i
sosu_cnt_lst[i] -= 1
for num in up_lst: # 다 나눈 수를 곱한다.
result *= num
print(result)
메모리 초과를 걱정해서 어렵게 접근해 해결했지만 파이썬은 오버플로우도 없고 그냥 분자를 다 곱해서 나누어도 메모리 초과가 일어나지 않는다고 한다... 괜히 어렵게 돌아가서 해결한 느낌..