[백준 11401] 이항 계수3 / 자바 / 수학(파스칼 + 모듈러)

#문제         

레벨: G1
알고리즘: 수학(파스칼 + 모듈러
풀이시간: 1시간 
힌트 참조 유무: 유

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

---

#문제 풀이        

 

이항 개수란 N개에서 순서상관없이 K개를 뽑는 것을 말한다. 보다시피 조합문제는 파스칼 문제로 치환된다. 그런데 N의 숫자가 상당하다 이정도의 파스칼을 구했다가는 어떠한 변수에도 담을 수 없다.(알고리즘 문제를 풀 때 12팩토리얼과 20팩토리얼은 각각 int와 long형이 넘어간다는 것을 알면 좋다.) 그래서 우리는 이 문제를 풀기위해서 크게 두가지를 구현해야 한다. 

그림1

1. 파스칼 수 구하는 법

2. 모듈러 연산(변수에 담기 위해) 

 

1. 파스칼 수 구하는 법

//일반 파스칼
main {
	print(factorial(N) / (factorial(K) * factorial(N - K)));
}

int factorial(int N) {
	if(N == 0) {
		return 1;
	}
	return N * factorial(N - 1);
}

---------------------------------------------
//파스칼 성질 이용  
main {
	print(BC(N, K));
}
 
int BC(int N, int K) {
 
	// 2번 성질
	if(N == K || K == 0) {
		return 1;
	}
    // 1번 성질
	return BC(N - 1, K - 1) + BC(N - 1, K);
}

-------------------------
//성능을 위해 dp 도입

int[][] dp = new int[N + 1][K + 1];
 
main {
	print(BC(N, K));
}
 
int BC(int N, int K) {
 
	// 이미 풀었던 sub문제일 경우 값을 재활용
	if(dp[N][K] > 0) {
		return dp[N][K];
	}
 
	// 2번 성질
	if(N == K || K == 0) {
		return dp[N][K] = 1;
	}
    // 1번 성질
	return dp[N][K] = BC(N - 1, K - 1) + BC(N - 1, K);
}

파스칼 구하는 법은 이렇게 3가지로 구현할 수 있다.2 번째 코드인 파스칼 성질을 이용해서 구현한 코드가 이해가 안 될 수 있으니 잠시 설명하겠다.

그림2를 봐보자. 한층의 너비의-1이 N이 되고 왼쪽부터 오른쪽까지 K(0 ~ N)가 되는 거다. 파스칼의 그림을 보면 그림3에 그려져있느 조합성질이 이해가 갈테다.

 

그림2

그림3

 

 

2. 모듈러 연산

모듈러의 성질은 이렇게 두가지가 있다. 증명을 여기서 풀기에는 너무 길이지기 때문에 각자 찾아보길 바란다. 알고리즘 테스트를 준비하고 있다면 모듈러 성질 2가지는 알아야 한다. 

근데 만약  위 두가지가 아니라 (a/b)mod m 은 위 성질을 이용할 수 없다. 나눗셈은 이 공식을 적용할 수 없기 때문이다. 그래서 우리는 b를 나눈다고 생각하는 것이 아니라 1/b를 곱한다고 생각해야 한다. 그래야 2번 성질을 적용할 수 있으니.  자 이제부터 1/b mod m 을 구해보자.

페르마의 소정리에 인해서 b의p-2승 (mod m)가 1/b(mod m)이다.

 

 

그리하여 문제의 식에 모듈러 식을 대입해보면 아래와 같이 도출된다.

 

 

 

---

#풀이 코드      

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        long[] factorial = new long[N + 1];
        factorial[0] = 1;
        for (int i = 1; i <= N; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }

        long numerator = factorial[N];
        long denominator = (factorial[K] * factorial[N - K]) % MOD;

        // Using Fermat's Little Theorem to find the modular inverse
        long result = numerator * modInverse(denominator, MOD) % MOD;

        System.out.println(result);
    }

    static long modInverse(long base, int mod) {
        return modPow(base, mod - 2, mod);
    }

    static long modPow(long base, int exp, int mod) {
        if (exp == 0) return 1;
        long half = modPow(base, exp / 2, mod);
        long halfSquared = half * half % mod;
        //모듈러 성질 2번에 의해
        //5^4 % 2 = (5^2 %2) x (5^2 %2) % 2 으로 치환 가능
        //제곱이 1이라면 
        if (exp % 2 != 0) {
            return halfSquared * base % mod;
        }
        return halfSquared;
    }
}