[Baekjoon]백준 11401 이항 계수 3(골드 1) - Python

문제설명

문제 자체는 이전에 풀었던 이항계수 문제들과 동일하지만, 분할 정복을 사용하여야한다는 차이점이 존재한다

일단 그래도 혹시나 싶어서 재귀함수를 사용하지 않고 팩토리얼을 계산하여 나머지를 출력하는 코드를 작성하였다

num, square = map(int, input().split())

def sol(num, square):
    if square == 0 or square == num:
        return 1
    elif square > num // 2:
        square = num - square
        
    result = 1
    for i in range(square):
        result = result * (num - i) // (i + 1)
    return result
    
print(sol(num, square) % 1000000007)

결과는 역시나 시간초과가 발생한다(글 작성하면서 다시 살펴보니 for문에서 나머지 연산도 빼먹었다)

이 문제를 어떻게 분할정복을 사용하여 풀이가 가능할까...?라는 생각을 해보다가 결국 검색찬스를 사용하였다

그리고 필요한 공식이 있었다 페르마의 소정리를 활용하면 조합 형식을 곱셈 형태로 변형할 수 있다

《《《  nCk​ % P = n! x ((n−k)!k!)^P−2 % P 》》》

팩토리얼의 값을 그대로 구할 수는 없기 때문에 이전 문제에서 사용하였듯

나머지 연산을 중간중간 해주면서 계산하면 된다

def pow_(A, B):
    if B == 0:
        return 1
    if B % 2 == 1: # 홀수인 경우
        return (pow_(A, B // 2) ** 2 * A) % P
    else:          # 짝수인 경우
        return (pow_(A, B // 2) ** 2) % P

문제에서 제곱을 활용하기 때문에 직접 재귀함수를 호출하며 제곱을 구하는 함수를 만들어주었고

factorial을 저장할 리스트를 따로 만들어주었다

factorial = [1 for _ in range(num+1)]

P = 1000000007 # 문제 조건
for i in range(2, num + 1):
    factorial[i] = factorial[i-1] * i % P

재귀적으로 호출하기보다는 동적 프로그래밍을 활용하여 효과적으로 계산하여 저장하였다

그리고 위에서 말한 공식을 사용하여 분자와 분모를 각각 설정해주고,

각각 나머지 연산한 결과를 곱해주고 나머지 연산을 해주면 된다

def pow_(A, B):
    if B == 0:
        return 1
    if B % 2 == 1: # 홀수인 경우
        return (pow_(A, B // 2) ** 2 * A) % P
    else:          # 짝수인 경우
        return (pow_(A, B // 2) ** 2) % P

num, K = map(int, input().split())

factorial = [1 for _ in range(num+1)]

P = 1000000007 # 문제 조건
for i in range(2, num + 1):
    factorial[i] = factorial[i-1] * i % P

numerator = factorial[num]
denominator = (factorial[num-K] * factorial[K]) % P

print((numerator % P) * (pow_(denominator, P-2) % P) % P)

수학공식의 필요성을 느끼게 된 문제였다