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

 

---

 

• 코드

정답 코드 : onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/를 참고해서 이해하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] factorial = new long[N+1];
        factorial[0] = 1;
        factorial[1] = 1;
       
        for(int i=2; i<=N; i++) factorial[i] = (factorial[i-1]*i)%1000000007;
        long denominator = (factorial[K]*factorial[N-K])%1000000007;

        long index = 1000000007-2;
        long fermatNum = 1;
        while(index > 0){
            if(index%2==1){
                fermatNum *= denominator;
                fermatNum %= 1000000007;
            }
            denominator = (denominator*denominator)%1000000007;
            index /= 2;
        }
        long result = ((factorial[N]%1000000007)*(fermatNum%1000000007))%1000000007;
        System.out.print(result);

    }
}

 

 

정답 코드 : 위의 코드보다 메모리도 1/4정도 잡아먹고, 속도도 위의 코드보다 좀 더 빠르다. 페르마의 소정리를 이용ㅇ해서 푼 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/* [페르마의 소정리] _ 혜민 코드 참고
a^(p-1) % p = 1
(a/b) % M = ((a % M) * (b^-1 % M)) = ((a % M) * (b^(M-2) % M))
*/

public class Main {
    static final int MOD = 1000000007;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long a = fac(N);
        long b = fac(N - K) * fac(K) % MOD;
        long result = a * pow(b, MOD - 2) % MOD;
        System.out.print(String.valueOf(result));
        
    }

    public static long fac(long n) {
        long result = 1;
        while (n > 1) {
            result = (result * n) % MOD;
            n--;
        }
        return result;
    }

    public static long pow(long a, int b) {
        long result = 1;
        long temp = a;

        while (b > 0) {
            if (b % 2 == 1) result = result * temp % MOD;
            b = b / 2;
            temp = (temp * temp) % MOD;
        }

        return result;
    }
}