[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)11401번, 이항 계수 3

문제 링크

11401번: 이항 계수 3

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

분할 정복 알고리즘은 일정한 간격으로 입력된 값을 분할하여 조건에 맞는지 확인하고 틀리면 다시 일정한 간격으로 분할하는 것을 반복하여 조건에 만족할 때까지 진행하는 알고리즘입니다.

 

처음에 문제를 접근할 때에는 이항계수의 파스칼 트리를 통해서 접근하였지만 시간 초과 때문에 실패하였습니다. 그 이후에 분할 정복을 사용하려면 어떻게 해야하는지 고민하다가 구글링을 통해 해답을 얻었습니다.

우선 알고리즘에서 사용할 것은 모듈러 연산과 페르마의 소정리를 이용하였습니다.

 

모듈러 산술이란?( n mod m = n을 m으로 나누었을 때 나머지라는 뜻입니다.)

(a+b) mod p = (a mod p + b mod p) mod p

(a-b) mod p = (a mod p - b mod p) mod p

(a*b) mod p = (a mod p * b mod p) mod p

이 공식은 나머지를 구하는 것도 결합/교환 법칙이 적용된다는 것을 보여주는 것입니다.

 

페르마의 소정리란?(n이 소수일 때만 만족)

aⁿ mod n = a mod n 입니다.

자세한 공식의 설명은 제가 참고한 사이트의 링크를 참고해주시면 감사하겠습니다.

모듈러 산술 - 위키백과, 우리 모두의 백과사전

 

ko.wikipedia.org

페르마의 소정리 - 나무위키

 

namu.wiki

이 문제에서는 이항계수의 값의 나머지를 구하여야 하기 때문에 식을 아래와 같이 표현할 수 있습니다.

n!/k!(n-k)! mod p   (p = 1000000007)

수학에서 분모 k!(n-k)!을 다르게 표현이 가능합니다.

아래와 같이 문제에 식을 표현할 수 있으며 이 상태를 모듈러 산술로 변경하면 됩니다.

n! mod p factorial을 진행하여 나머지를 구하면 되지만 n!(n-k)!에 관련된 연산을 수행하기 힘들다.

여기서 페르마의 소정리를 사용하였습니다.

페르마의 소정리의 공식을 아래와 같이 유도할 수 있습니다.

유도한 공식을 위에 공식에 적용시킨다면

위 공식을 적용시켜서 이항계수의 공식을 표현하면

이제 해결 알고리즘을 살펴보면

1. n!와 k!(n-k)!을 반복를 통하여 구합니다.

2. k!(n-k)!의 p-2의 계수만큼 제곱한 값을 구합니다.(p는 소수입니다)

3. 두 값을 곱한 뒤 다시 나머지를 구하여 결과를 출력합니다.

※ 수를 곱할 때는 모듈러 산술로 인하여 나머지를 구하는 연산도 모두 포함되어야 합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 N, K를 저장하였습니다.
• 팩토리얼/이항 계수/계수 제곱을 구하는 factorial/binomialCoefficient/mul함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 이항계수의 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• factorial함수에서 반복문을 통하여 메모이제이션에 팩토리얼 값을 저장하였습니다.
• binomialCoefficient함수에서 위에 공식 모듈러 산술과 페르마 소정리로 유도된 공식을 구하였습니다.
• mul함수에서 p-2만큼 계수의 제곱의 값에 나머지를 구하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static long[] arr;		//팩토리얼 메모이제이션
	static int p = 1000000007;	// 나누는 값, 소수
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장------------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        factorial(N);		//팩토리얼 함수 수행
        long molecules = arr[N] % p;	//n! 구하기
        long denominator = arr[K] * arr[N-K] % p; //k!(n-k)! 구하기
        bw.write(binomialCoefficient(molecules, denominator) + "\n");	//결과 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //------메모이제이션에 팩토리얼 값 저장하는 함수----------
    public static void factorial(int n) {
    	arr = new long[n+1];
    	arr[0] = 1;
    	arr[1] = 1;
    	for(int i=2;i<=n;i++)
    		arr[i] = i * arr[i-1] % p;
    	
    }
    //----------이항 계수 구하는 함수---------
    public static long binomialCoefficient(long N, long K) {
    	long temp = mul(K, p-2);
    	return N * temp % p;
    }
    //---------계수 제곱을 수행하는 함수---------
    public static long mul(long n, int depth) {
    	if(depth==1)
    		return n % p;
    	
    	long temp = mul(n,depth/2);
    	
    	if(depth%2 == 0) {	//계수가 짝수일 때
    		return temp * temp % p;
    	}
    	else		//계수가 홀수일 때
    		return (temp * temp % p) * (n % p) % p; 
    }
}