[JAVA] 백준 11401 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

- 자연수 N과 정수 K가 주어졌을 때 이항 계수를 1,000,000,007로 나눈 나머지를 구하는 프로그

 

 

 

 

문제 풀이 

이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리 (velog.io)

이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리

 

- 이항 계수란 n개의 원소에서 k개의 원소를 뽑아내는 경우의 수를 의미하며, 공식은 다음과 같다. 

 

출처 -  이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리 (velog.io)

 

- 일반적으로 이항 계수 문제를 풀 때는 nCr = n-1Cr-1 + n-1Cr 공식을 이용하여, 메모이제이션하여 O(n^2) 시간 복잡도로 해결할 수 있다. 

 

- 그러나 이 문제에서는 N의 범위가 매우 커서 O(N^2)의 시간복잡도로는 풀 수 없다. 

- 조합 공식 nCr = n!(n-r)!r!로 문제를 접근 

- 나누기 연산이 들어간 식을 곱셈 연산으로 된 식으로 변형시키는 방법이 필요하고, 이때 필요한 것이 페르마의 소정리 이다. 

페르마의 소정리 

 

- 이항 계수에서 n과 r의 값이 커지면 경우의 수도 매우 많아진다. 그렇기 때문에 경우의 수에 모듈러 연산을 취한 값을 원하는 경우가 있다. 

- 이때 페르마의 소정리를 이용하면 이항계수를 빠르게 구할 수 있다. 

 

- 페르마의 소정리란, p가 소수이고 a가 정수일 때 , 다음을 만족한다는 것

출처- 이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리 (velog.io)

 

- 해당 공식의 의미는 ap를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 것이다. 

- 여기에서 양변을 a로 나누어 주면 다음과 같은 식을 얻을 수 있다. 

출처- 이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리 (velog.io)

 

- 페르마의 소정리를 이항 계수에 적용시켜보면

- nCr = n!/(r!(n-r)!) (mod p)일때, A = n!, B=(r!(n-r)!)이라 대입

- n!/(r!(n-r)!)%p = (A*B-1)%p = ((A%p)*(B-1%p))가 된다. 

- B-1은 Bp-2와 같은 값이 된다. 

- 즉 nCr = (A*Bp-2)%p라는 공식이 나오게 되며, 분수가 아닌 정수의 곱으로 이항계수를 표현할 수 있게 됨 

 

[백준] 11401번 : 이항 계수 3 - JAVA [자바] (tistory.com)

[백준] 11401번 : 이항 계수 3 - JAVA [자바]

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    
    final static long P = 1000000007;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Long N = Long.parseLong(st.nextToken());
        Long K = Long.parseLong(st.nextToken());
        
        //분자 N!
        long numer = fac(N);
        
        //분모 (K!*(N-K)!)mod p
        long denom = fac(K)*fac(N-K)%P;
        
        //N! * 분모의 역원((K! * (N-K)!)
        bw.write(numer*pow(denom,P-2)%P+"");
        bw.flush();
        bw.close();
    }
    
    //팩토리얼
    static long fac(long N)
    {
        long fac = 1L;
        
        while(N>1)
        {
            fac = (fac*N)%P;
            N--;
        }
        return fac;
    }
    
    //역원
    //base: 밑, expo:지수
    static long pow(long base, long expo)
    {
        long result =1;
        
        while(expo>0)
        {
            //지수가 홀수면 반환하고자 하는 result에 곱해주도록 함
            //지수가 모두 짝수라면 expo가 1이 될때까지 base의 값이 제곱되다가 최종적으로 result에 담김
            if(expo%2==1)
            {
                result *=base;
                result %=P;
            }
            base = (base*base)%P;
            expo /=2;
        }
        return result;
    }
}