[SWEA] 5607.[Professional] 조합 (python)

📌문제

💪아이디어

1. 조합 계산
   
   조합관련 문제이므로 펙토리얼을 구현하려고 하였다. python에는 combination값을 계산하는 math.comb(n,r)함수가 있어서 사용하려하였지만 n의 최대값이 1e6이었기 때문에 시간초과가 나타났다. 그래서 직접 펙토리얼을 구현해야했다.
   
   

2. factorial 구현
   
   $Combination(n,r) = \frac{n!}{(n-r)!r!}$ 을 구현해야 했기에 처음에는 재귀함수를 사용하였다.

def fact(n):
    if n==0 or n==1: return 1
    return n * fact(n-1)

재귀 호출의 깊이 제한으로 인하여 스택 오버플로우가 발생하여 다른 방법을 찾아야 했다. 그래서 밑 코드와 같이 memorization를 사용하여 펙토리얼 값을 계산하였다.

arr = [1, 1]
def fact(n):
    for i in range(2, n+1):
        arr.append(arr[-1] * i)

테스트케이스마다 펙토리얼배열을 구하는 것은 중복된 계산을 수행하게 되어 비효율적(O(T*n))었다. 그래서 테이스케이스를 입력받아 최댓값을 찾고 최댓값만큼의 펙토리얼배열을 구하여 재사용하였다.(한번만 펙토리얼배열을 찾으면 모든 값을 구할 수 있기 떄문이다.(O(n)))

🥂코드

arr = [1, 1]
def fact(n):
    for i in range(2, n+1):
        arr.append((arr[-1] * i) % 1234567891)

T = int(input())
li = []
max_val = 0

for i in range(1, T+1):
    n, r = map(int, input().split())
    max_val = max(n, r, max_val)
    li.append((n, r))

fact(max_val)

for i, val in enumerate(li):
    a, b = val
    answer = (arr[a] * pow((arr[a-b] * arr[b]) % 1234567891, 1234567889, 1234567891)) % 1234567891
    print('#{} {}'.format(i+1, answer))