알고리즘

[알고리즘-이항계수] 백준 11401번: 이항계수3 자바

롱2롱 2023. 4. 26. 17:29

이항계수가 먼데 십덕앙... 

 

이항계수란?

N개의 원소에서 K개의 원소를 뽑아내는 경우의 수! (=조합)

 

nCk = n-1Ck + n-1Ck-1 

위의 식을 일반화 하면 이렇게 되는데 내가 n중에서 k개를 뽑고 싶다는 것은 하나를 일단 뽑고 나머지에서 남은 것을 뽑을거다랑 그 원소를 선택하지 않고 뽑는 경우의수를 더한 것임

예를 들면 1-10까지 자연수 중 총 4개를 뽑는다고 가정할 때 공식으로는 10C4

이때 내가 1을 뽑고 나머지 9개에서 3개를 뽑는 것과 1을 뽑지 않고 나머지 9에서 4를 뽑는 것은 절대 겹치지 않는 경우의 수임 그리고 결국 두개를 더해야 10개중에서 4개를 뽑았을 때 전체 경우의 수가 나옴 !

 

그래서 이걸 저장해놓고 사용하는 memorization을 중심으로 푸는 문제인줄 알았는데 이항 계수를 메모리로 풀어도 모듈러 할 때 이항계수 값이 너무 크면 연산이 너무 커지는 걸 알아챘어야 했다~ 이항계수보다 중요한건 페르마의 소정리였음 ㅜ 

 

 

그건 또 먼데 십덕앙...

페르마의 소정리란?

정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수일때 다음이 성립한다

≡는 합동을 의미함 a^p를 p로 나눈 나머지는 a를 p로 나눈 나머지와 같다

 

이걸 또 a로 나눠주면 다음 식이 됨

 

다시 문제로 돌아오면 결론은 

p = 1,000,000,007

을 풀어야 한다는 것 

위의 페르마의 소정리 공식과 결합해서 풀려면 우선 모듈러 연산은 분배법칙이 적용X, 곱셈 분배 법칙은O 를 알야아함 ~ (제가 그걸 어케 아나요~)

 

밑의 식을 공식에 적용할 수 있게 유도하려면 일단  나누기를 곱으로 바꿔주고 곱셉 분배 법칙을 적용해주면 익숙한 넊김이 드는데 a^-1(mod p) ≡ a^p-2로 바꿔주면 된다 ~

 

이걸 토대로 코드를 짜보면

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
백준 11401번: 이항 계수3
start : 2023-04-26 14:00
end : 2023-04-26 16:18
 */
 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BJ_11401 {
 
        public static int n, k, r;
        public static int[][] arr;
        final static long P = 1000000007;
 
 
        public static void main (String args[]) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(bf.readLine());
 
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
 
            long N = fact(n);
            long K = fact(k) * fact (n-k) % P;
 
            System.out.println(N*pow(K, P-2)%P);
 
 
        }
 
        public static long fact (long n){
            long fac = 1L;
            while (n>1){
                fac = (fac*n)%P;
                n--;
            }
            return fac;
        }
 
        public static long pow (long base, long expo){
            if (expo == 1){
                return base % P;
            }
            long temp = pow(base, expo/2);
            if (expo%2 ==1){
                return (temp*temp%P)*base %P;
            }
 
            return temp * temp % P;
        }
 
}
 
 cs

 

참고한 사이트
https://nicotina04.tistory.com/65
https://st-lab.tistory.com/241
https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-11401%EB%B2%88-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-3-Java-Python