[BOJ] 11401. 이항 계수 3 - JAVA (페르마의 소정리)

🔗 문제

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

11401번: 이항 계수 3

 

💻 풀이 및 코드

문제 유형 : 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셉 역원, 페르마의 소정리

 

nCr 를 1,000,000,007 로 나눈 값

 

풀이

나는 간략하게 핵심만 정리할 거라 이해가 안된다거나 더 자세한 설명을 원한다면 

https://st-lab.tistory.com/241

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

에서 잘 설명해놔서 여기를 참고하는 게 나을 것 같다.

 

---

먼저, nCr 는 다음과 같다.

조건에서 n 과 r 의 최댓값은 4,000,000 이므로 4,000,000! 은 long범위를 아득하게 넘는다. (참고로 20! 만 되어도 long 범위를 넘어간다.) 

즉, (n! / r! (n-r)!) % 1,000,000,007 을 출력해야 한다.

 

여기서 문제가 될 게 모듈러 연산에서 나눗셈 연산은 없다

 

번거롭기 때문에 1,000,000,007 을 P 로 나타내면

즉,  (n! % P) / (r! (n-r)!) % P  와 같이 분배법칙이 적용이 안돼서 이렇게 계산할 수 없다는 뜻이다.

 

그렇다면 어떻게 풀어야 하는가?

먼저, 모듈러 연산에서 곱의 분배 법칙은 적용이 된다는 것을 알고 있을 것이다.

우리가 분수 때문에 분배 법칙을 사용하지 못하지 않았는가? 즉, 좀만 돌아서 생각해보면 분수 형식을 곱셈 꼴로 만들면 된다는 것이다.

 

곱셈꼴로 어떻게 만들어야 하지? 쉽게 생각해보면 역원을 이용하여 곱셈 꼴로 만들면 된다.

쉽게 생각해보면 이렇다.

분수를 역원으로 바꾸면 곱셈 꼴로 변환되기 때문에 모듈러 연산의 곱셈에 대한 분배법칙을 적용 할 수 있다.

즉, 다음과 같은 꼴로 변환하여 적용한다는 것이다.

 

 

이제 (K! (N-K)!) 의 역원을 구하는 것이 관건이다.

여기에서 바로 '페르마의 소정리' 를 적용해야 한다. 

(사실 난 페르마의 소법칙의 증명을 자세히 안들여다봤다.간략하게 말하면 다음과 같다.)

괄호 때문에 햇갈렸는데 그냥 괄호는 무시하고 보면 된다.

a 가 (K! (N-K)! ) 으로 대치된다면 다음과 같다.

따라서 최종 공식은 다음과 같다.

이제 코드로 구현해보자.

여기서 N! 은 쉽게 구할 수 있다.

static long factorial(int N) {
    long res = 1l;

    while(N>1) {
        res = res * N % P;
        N--;
    }
    return res;
}

을 구하는 방법에서 분할정복이 사용이 된다. 

이 방에는 재귀를 사용하는 방법과 반복문을 사용하는 방법 2가지가 있다.

 

1) 재귀

static long pow(long base, int expo) {
    if(expo == 1) {
        return base % P;
    }

    long res = pow(base, expo/2);
    res = res*res%P;

    if(expo%2 == 0) return res;
    return res*base%P;
}

2) 반복문

public static long pow(long base, int expo) {
    long res = 1;    

    while (expo > 0) {

        if (expo % 2 == 1) {
            res *= base;
            res %= P;
        }
        base = (base * base) % P;
        expo /= 2;
    }

    return res;
}

 

이제 전체 코드를 보면 이해가 갈 것 같다.

 

느낀 점

• 역원을 구할 땐 페르마의 소정리를 사용하자
• 거듭제곱을 구할 때 분할정복을 통해 빠르게 계산할 수 있다. 재귀를 사용하는 방법과 반복문을 사용하는 방법 2가지가 있다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_11401_이항계수3 {
	
	static int P = 1_000_000_007;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_11401.txt"));
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		// N! (분자)
		long numer = factorial(N);
		
		// K!(N-K)! % P (분모)
		long denom = factorial(K) * factorial(N-K) % P;
		
        	// 페르마의 소법칙을 사용해 역원을 곱한 값을 출력
		System.out.println(numer * pow(denom, P-2) % P);
		sc.close();
		
	}
	
	static long factorial(int N) {
		long res = 1l;
		
		while(N>1) {
			res = res * N % P;
			N--;
		}
		return res;
	}
	
	static long pow(long base, int expo) {
		if(expo == 1) {
			return base % P;
		}
		
		long res = pow(base, expo/2);
		res = res*res%P;
		
		if(expo%2 == 0) return res;
		return res*base%P;
	}

}

---

Reference

https://st-lab.tistory.com/241

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