[BAEKJOON] 11401 이항 계수 3

문제 요약

• 알고리즘 분류: 수학, 조합, 재귀호출
• 난이도: Gold2
• 문제내용:
  • 조합한 결과를 1,000,000,007로 나눈 나머지를 출력해라

• 사이트 : https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

문제풀이

 이번 문제 내용은 간단한데 데이터의 범위가 4,000,000 이라서 O(N)으로 풀어도 데이터 저장할수 있는 숫자와 배열의 크기가 넘어 갈뿐만 아니라 메모리도 초과 되어서 다른 방법으로 접근 해야 한다. 

문제 접근 방법

 정상적인 DP 방법으로도 안되서 나머지 정리를 이용한 문제를 풀어야 한다. 나머지 정리중 페르마의 소정리가 있다.

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

 a 제곱 한것과 그냥 a 를 똑같은 수를 나눈 나머지는 같다. 즉  (a * a *  ... * a) % p = a % p 이라는 것이고 p는 소수이고 a가 p의 배수가 아닐때 가능 한 식이다. 그러면 a ^ p % p = a % p도 성립이 된다.

  정리한다면,  a ^ p % p ≡ a % p  = a  ^ (p - 1) (mod p) ≡ 1 (mod p)라는 결과가 나온다.

  그럼 조합의 공식을 보면 nCr = (n!) / (r! * (n - r)!) 인데 분자 분모에다가 나머지를 적용 할수가 없다. 그래서  곱셈을 적용한 식으로 가야한다. 

  (n!) / (r! * (n - r)!)  = (n!) * (r! * (n - r)! ^ -1 로 나타 낼수가 있다. 여기서 나머지를 구한 결과를 식으로 표현한다면

  ((n!) % p) * (r! * (n - r)! ^ -1 % p) = ((n!) % p) * (r! * (n - r)! ^ (p - 2)) % p 로 결론이 난다.

r! * (n - r)! ^ (p - 2) 이 식이 나온는 이유는  a  ^ (p - 1) (mod p) ≡ 1 (mod p) 이 부분에서 응용한 것이다. 

r! * (n - r)! ^ (p - 1) * r! * (n - r)! ^ - 1 = r! * (n - r)! ^ (p - 2) 으로 만들수 있다.

 위에 식이 정리 되었다고 끝이 아니다. 두번째 문제는 1,000,000,007 제곱해서 처리하는 문제이다.  그냥 하면 처리하면 데이터 값이 초과 되고 1 ~ 1,000,000,007  for 문으로 돌려서 나머지 연산 하면 시간 초과로 인한 문제가 발생한다. 그래서 분할로 처리 하는 방식으로 할것이다. a ^ p = a ^ p / 2 * a ^ p /2로 처리가 가능해서 p /2 를 제곱한 결과만 알면 된다. p를 2로 나눠서 1될때 까지의 결과 값을 2번씩 곱해서 처리하면 된다. 하지만 p가 홀수 일때와 짝수일 때를 나눠서 처리 해야 하는데 아래와 같은 식으로 처리하면된다.

 정리

1. 조합의 기본적인 n!, r! * (n - r)! 부터 구한다. factorial 계산할때 중간에 % p를 해줘야한다.
2. 재귀 호출로 r! * (n - r)! ^ (p - 2) 값을 구한다.
3. 재귀 호출에서 p -2 는 2로 계속 나누어서 제곱한 결과를 2번 곱하면서 % p 연산을 해주면 된다.

Code

Python

 파이썬은 pow라는 내장 함수 있어서 제곱해서 처리하는 부분에서 따로 구현 할 필요가 없다.

def factorial(n):
    result = 1
    while(n > 1):
        result = result * n % P
        n -= 1
    return result
    
P = 1000000007
N, K = map(int, input().split())
print(factorial(N) * pow(factorial(N - K) * factorial(K) % P, P - 2, P) % P)

Java

 위에 파이썬과 다르게 자바는 중간에 처리해야 될 부분이 있다. 그 이유는 기본 정수형 타입중 long이 제일 큰데 연산한 결과 중간에 나머지 연산안하면 값이 초과가 되어서 이상한 결과값이 나올수 있기 때문이다. 중간에 나머지 연산을 중간에 넣으면서 구현을 해야된다.

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

public class Main {
	
	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 = Integer.parseInt(st.nextToken());
		long K = Integer.parseInt(st.nextToken());
		
		System.out.println(factorial(N)  * FIT(factorial(N - K) * factorial(K) % P, P - 2)  % P );
		System.out.println(Integer.MAX_VALUE);
	}
	
	public static long factorial(long n) {
		
		long result = 1L;
		
		while(n > 1) {
			result = (result * n) % P;
			n--;
		}
		return result;
	}
	
	// base: 밑, expo: 지수
	public static long FIT(long base, long expo) {
		
		
		if(expo == 1) return base % P;
		
		long result = FIT(base, expo / 2);
		
		result = result * result % P;
		
		if(expo % 2 == 1) return result * base % P;
		else return result;
	}
	
}