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

 
www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

이 전에 풀었었던 정수론 및 조합론 카테고리의 이항 계수 2 문제를 풀었다면 크게 어려움 없이 풀었을 것이다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제는 이 전에 이미 설명해줬기 때문에 내용이 거의 중복될 것이다.

 

 

 

 

일단 문제를 풀이하기 전에 아래 글을 읽고 오시는 것을 추천드린다.

 

st-lab.tistory.com/162

[백준] 11051번 : 이항 계수 2 - JAVA [자바]

 

 

 

 

 

일단, 이 문제를 풀기 위해서는 모듈러 연산과 페르마의 소정리를 알고 있어야 한다.

 

 

일단, 이항계수를 구하는 방법은 다음과 같았다.

 

 

 

문제는 위 식에서 1,000,000,007 로 나눈 나머지 값을 출력해야한다는 것이다.

 

즉, 모듈러 연산을 이해해야 하는데, 주어지는 N과 K는 최대 4,000,000 으로, 단순하게 분자의 N! (4,000,000!) 만 구하더라도 long범위를 아득하게 넘는다. (참고로 long타입으로 연산하더라도 20! 만 되어도 long 범위를 넘어간다.)

 

주어진 문제를 보면 결국 (n! / r! (n-r)!) 을 1,000,000,007 로 나눈 나머지 값, 즉, (n! / r! (n-r)!) % 1,000,000,007 을 구해야 한다는 것이다.

만약, 입력으로 주어지는 N이나 K가 20 미만의 수로 입력 된다면 위 식의 순서대로 각 팩토리얼 값을 구한 뒤, 총 구해진 값에 모듈러 연산을 통해 나눈 나머지 값을 출력해도 문제가 없지만, 문제에서 주어지는 입력은 너무 크다는 것을 알 수 있을 것이다.

 

결국에는 모듈러의 연산 공식을 활용해야 하는데,

 

*여기서 가장 중요한 점이 있다.

모듈러 연산에서 나눗셈 연산은 '없다'

 

즉, 나눗셈(분수 꼴)의 수에 대한 모듈러 연산은 분배법칙을 적용 할 수가 없다는 뜻이다.

 

N과 K, 그리고 나누는 수인 1,000,000,007을 p로 표현하면 다음과 같은 말이다.

 

 

즉, 분수 꼴에서는 위와 같이 분배법칙을 사용하지 못한다.

 

 

 

그러면 어떻게 풀어야 하는가?

 

모듈러 연산 기본 성질에서 곱셈의 분배 법칙은 성립한다는 것은 다들 알고 있을 것이다. 

 

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

 

 

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

 

쉽게 생각해보면 이렇다.

 

즉, 분수 꼴을 곱셈 꼴로 만들기 위해서는 x에 대한 역원을 구하면 된다는 것이다.

 

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

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

 

 

즉, 우리는 (K! (N-K)!) 의 역원을 구하는 것이 관건이다.

분모의 값을 지수로 -1 지수로 표현하더라도, 분수는 분수이기 때문이다.

 

즉, 역원을 통해 분수가 아닌 정수 곱셈으로 표현될 수 있어야 한다.

 

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

 

 

[페르마의 소정리] (링크 : ko.wikipedia.org/wiki/페르마의_소정리)

 

페르마의 소정리의 정의는 다음과 같다.

 

참고로 a ⫮ p 에서 ⫮ 기호는 '나눠지지 않음'이라는 뜻, 즉, a는 p의 배수가 아니라는 말이다. 

 

 

위 식을 보조정리를 이용하여 다음과 같이 표현할 수 있다

 

.

 

즉, a (mod p) 에 대한 역원은 a^p-2 (mod p) 이라는 것이다.

 

그럼 우리가 구하려던 역원 식을 a로 대치해보면 다음과 같다.

 

 

즉, (K! (N-K)!)1000000007-2 는 정수로 표현되기 때문에 이제 이를 곱셈 분배 법칙으로 변환하여 만들 수 있다.

 

최종적으로, 구해지는 식은 다음과 같아진다.

 

 

 

 

위 방식을 통해서 답을 구해주면 된다.

 

 

 

그럼 방식을 알았으니, 분할정복은 어디에 이용되는가?

 

바로 (K! (N-K)!) 1000000007-2 , 즉 제곱을 구하는 곳에 쓰이는 것이다.

 

 

바로 분할정복에서 직전 문제였던 곱셈 (st-lab.tistory.com/237) 문제에서 어떻게 분할정복을 하는지 볼 수 있었다.

바로 거기서 분할정복이 이용되는 것이다.

 

 

즉, 역원을 구하는, 사실상 (N-K)를 p-2 승만큼 제곱하는 알고리즘에서 분할정복이 쓰이는 것이다.

 

 

결과적으로 제곱 방식은 마찬가지로 두 가지 방식이 있는데, 하나는 재귀 방식, 또 하나는 반복문 방식의 분할정복 법이 있다.

 

일단, 재귀 방식은 다음과 같이 짜면 되는 것이다.

 

<알고리즘 1>

 

public static long pow(long base, long expo) {
	// 지수가 1일 경우 base^1 이므로 base % P를 리턴
	if(expo == 1) {
		return base % P;
	}
		
	// 지수의 절반에 해당하는 base^(expo / 2) 을 구한다.
	long temp = pow(base, expo / 2);
		
	/*
	 * 현재 지수가 홀 수 였다면
	 * base^(expo / 2) * base^(expo / 2) * base 이므로
	 * base를 한 번 더 곱해주어야 한다.
	 * 
	 * ex) A^9 = A^4 * A^4 * A
	 */
	if(expo % 2 == 1) {
		return (temp * temp % P) * base % P;
	}
	return temp * temp % P;
		
}

 

 

 

위 방식을 반복문으로 짜면 다음과 같겠다.

 

 

 

 

<알고리즘 2>

 

public static long pow(long base, long expo) {
    long result = 1;    
	    
    while (expo > 0) {
	    	
    	// 지수가 홀 수면 밑을 한 번 더 곱하여 지수가 짝수가 되도록 한다.
        if (expo % 2 == 1) {
            result *= base;
            result %= P;
        }
        base = (base * base) % P;
        expo /= 2;			// 지수를 절반으로 나눔
    }
    return result;
}

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다. (사실 위 참고 링크를 모두 보고 오셨다면 아마 금방 풀으셨을 것이다.)

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

 

이 번 문제는 입력은 Scanner을 안 쓰고 BufferedReader로 통일하여 풀 것이다. 대신 분할 정복인 만큼 재귀로 제곱을 구현하는 방법과 반복문으로 구현하는 방법을 사용하여 풀어볼 것이다.

 

 

 

1. 알고리즘 1 (재귀)

2. 알고리즘 2 (반복문)

 

 

 

 

---

• 풀이

- 방법 1 : [알고리즘 1 (재귀)]

 

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

public class Main {

	final static long P = 1000000007;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		long N = Long.parseLong(st.nextToken());
		long K = Long.parseLong(st.nextToken());
		
		// 분자 N!
		long numer = factorial(N);
		
		// 분모 (K! * (N-K)!) mod p
		long denom = factorial(K) * factorial(N - K) % P;	
	
		
		// N! * 분모의 역원((K! * (N-K)!) 
		System.out.println(numer * pow(denom, P - 2) % P);
		
	}
	
	
	// 팩토리얼 함수 
	public static long factorial(long N) {
		long fac = 1L;
		
		while(N > 1) {
			fac = (fac * N) % P;
			N--;
		}
		return fac;
	}
	

	/*
	 * 역원 구하는 함수 
	 * 
	 * base : 밑,   expo = 지수 (exponent)
	 * 
	 * 거듭 제곱을 분할 정복 방식으로 푼다.
	 * 
	 */
	public static long pow(long base, long expo) {
		// 지수가 1일 경우 base^1 이므로 base % P를 리턴
		if(expo == 1) {
			return base % P;
		}
		
		// 지수의 절반에 해당하는 base^(expo / 2) 을 구한다.
		long temp = pow(base, expo / 2);
		
		/*
		 * 현재 지수가 홀 수 였다면
		 * base^(expo / 2) * base^(expo / 2) * base 이므로
		 * base를 한 번 더 곱해주어야 한다.
		 * 
		 * ex) A^9 = A^4 * A^4 * A
		 */
		if(expo % 2 == 1) {
			return (temp * temp % P) * base % P;
		}
		return temp * temp % P;
		
	}
	

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

팩토리얼과, 거듭제곱 모두 각각 풀어보았던 문제라 그리 어렵지 않을 것이다.

 

 

 

 

 

---

- 방법 2 : [알고리즘 2 (반복문)]

 

 

 

분할 정복을 재귀가 아닌 반복문으로 구현하는 것을 채택한 방식이다.

이 방법으로 구현하는 것도 그렇게 어렵진 않을 것이다.

 

 

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

public class Main {

	final static long P = 1000000007;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		long N = Long.parseLong(st.nextToken());
		long K = Long.parseLong(st.nextToken());
		
		// 분자 N!
		long numer = factorial(N);
		
		// 분모 (K! * (N-K)!) mod p
		long denom = factorial(K) * factorial(N - K) % P;	
	
		
		// N! * 분모의 역원((K! * (N-K)!) 
		System.out.println(numer * pow(denom, P - 2) % P);
		
	}
	
	
	// 팩토리얼 함수 
	public static long factorial(long N) {
		long fac = 1L;
		
		while(N > 1) {
			fac = (fac * N) % P;
			N--;
		}
		return fac;
	}
	
	
	/*
	 * 역원 구하는 함수 
	 * 
	 * base : 밑,   expo = 지수 (exponent)
	 * 
	 * 거듭 제곱을 분할 정복 방식으로 푼다.
	 * 
	 */
	public static long pow(long base, long expo) {
	    long result = 1;    
	    
	    while (expo > 0) {
	    	
	    	// 지수가 홀 수면 반환하고자 하는 result에 곱해주도록 한다.
	    	// 지수가 모두 짝수라면 expo가 1이 될 떄까지 base의 값이 제곱되다가 최종적으로 result에 담긴다.
	        if (expo % 2 == 1) {
	            result *= base;
	            result %= P;
	        }
	        base = (base * base) % P;
	        expo /= 2;
	    }
	    return result;
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 20597227  -  방법 2 : 알고리즘 2 (반복문)

채점 번호 : 20597227  -  방법 1 : 알고리즘 1 (재귀)

 

 

 

반복문과 재귀 방식 중 어떤 것을 사용하더라도 성능상의 큰 차이를 보이진 않는 듯 하다.

 

 

 

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다.

 

이미 풀어본 문제들(이항 계수, 거듭제곱 분할 정복법)을 응용하는 문제라 조금만 생각하면 금방 풀 수 있는 문제였다.

물론 페르마의 소정리를 증명하지 못해서 조금 어려울 수는 있다. 그렇다고 증명하기엔 내용이 길어져서 굳이 증명은 하지 않았다. 만약 증명을 모르더라도 저 역원 구하는 공식 하나는 외워두면 나중에 꽤 도움이 될 것이다.

 

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.