백준 11401 풀이 (이항 계수 3, 페르마의 소정리, 정수론, 분할알고리즘)

이번 문제는 너무나 어려웠다. 처음에는 어떻게든 풀어보려고 이항계수 강의도 듣고, 페르마의 소정리도 찾아보며 어떻게 풀어야할지 고민하기 시작했다. 물론 이게 하루이틀이지 계속 생각해도 안풀려서 고수의 도움을 받았다ㅋㅋㅋㅋ

 

여튼 내가 이해한 것을 천천히 정리해보자.

문제를 보면 1초의 시간제한이 존재한다. 또한 N값이 4,000,000으로 상당히 큰 수이다. 마지막으로는 1,000,000,007로 나눈 값을 출력하면 된다.

우선 이항계수를 공부하며 몇가지 규칙을 알게 되었다.

이항 계수를 한방에 이해할 수 있는 파스칼의 삼각형이다. 여기를 보면 규칙을 찾을수 있다.

규칙은 nCk = n-1Ck-1 + n-1Ck 이며 이것을 구하는 식을 나타내면 아래와 같다.

그러나 문제는 이러한 방식으로 엄청나게 큰 수를 찾는것은 상당히 어렵다. 따라서 이렇게 시도해본 결과 시간초과가 났다.

그래서 좀더 다른 방식의 접근이 필요하다. 따라서 처음으로 돌아가 본다.

나는 p로 나눈 나머지를 구해야한다. 문제는 분자와 분모를 나누려고 할때 분모가 0으로 나누어 떨어져버릴 수 있다. 그러면 분모가 0이 되어 성립하지 않게 된다. 그렇다면 다른 방식으로 해결해야한다.

따라서 이때 페르마의 소정리를 이용해야한다.

문제 페이지를 보면 친절하게 페르마의 소정리를 사용하라고 알려준다. 따라서 페르마의 소정리를 간단하게 공부해보자.

페르마의 소정리는 p가 소수이고 a가 정수일때

p에서 a^p와 a는 서로 합동이다.

a^p ≡ a (mod p)

(*합동이란 도형의 크기와 모양이 서로 일치한다는 뜻이지만, 정수론에서는 m으로 나눈 나머지가 동일하다는 뜻이다. 즉, 26 ≡ 5 (mod 3), 즉 26과 5는 3으로 나누면 같은 나머지를 같는다. 따라서 둘이 합동이라는.....그런 내용......(문과라 제가 이해한게 정확한지는 모르겠습니다.))

그럼 페르마의 소정리 식을 조금 변형해보면 분수를 나누더라도 같은 나머지를 갖게 할 수 있다.

$$a^{p-1} = 1 (mod p)$$

$$a^{p-2} = a^{-1}(mod p)$$

 

그러면 우리는 a에 p-2승을 하면 분수의 나머지를 구할 수 있다는 것을 알 수 있다. 즉, 1/a를 p로 나눈 나머지 값은 a^(p-2)를 p로 나눈 나머지와 같다는 것이다. 그렇다면 저걸로 치환하면 0이 아닌 나머지를 구할 수 있다.

분모가 0으로 변하지 않게 된다.

1. 팩토리얼 값은 그냥 loop문으로 구한다.

2. 거듭제곱은 분할 알고리즘을 활용한다. (백준 1629 풀이 참조)

3. 계산해준다.

이를 토대로 코드를 짜면 아래와 같다.

(*이때 중요한 것은 p로 중간 중간 나누어 줘야 오래 걸리지 않는다.)

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

def pactori(n,p):
    sum = 1
    for i in range(2,n+1):
        sum *= i
        sum %= p
    return sum


def div(a, b, p):
    if b == 1:
        return a % p
    tmp = div(a,b//2,p)

    if b % 2 == 1:
        return tmp**2 * a % p
    else:
        return tmp**2 % p

p = 1000000007
tmp = (pactori(n,p) % p) * div(pactori(n-k,p)*pactori(k,p),p-2,p) % p
print(tmp)

이상 문과출신의 허접한 풀이였습니다.