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

이항 계수 2  

 

문제

자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 1,000, 0 ≤ K\(K\) ≤ N\(N\))

 

출력

 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

 

예제 입력 1 

5 2

예제 출력 1 

10

 

---

처음엔 아래의 공식을 이용했다.

분자, 분모를 각각 factorial 함수로 계산했는데 n이 커질수록 int의 최대 범위를 넘어나서 틀렸다.

public class Main {

	public static int factorial(int num, int cnt) {
		if (num == 0 || cnt == 0) {
			return 1;
		}
		return num * factorial(num - 1, cnt - 1);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		K = N - K > K ? K : N - K;
		int result = (factorial(N, K) / factorial(K, 1)) % 10007;

		bw.write(result + "");

		bw.flush();
		bw.close();
		br.close();
	}
}

 

---

다음으로는 아래의 공식을 이용했으나 시간 초과로 실패했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static int combi(int n, int k) {
		if (k == 0 || n == k) {
			return 1;
		}

		return combi(n - 1, k - 1) + combi(n - 1, k);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		K = N - K > K ? K : N - K;

		bw.write(combi(N, K) + "");

		bw.flush();
		bw.close();
		br.close();
	}
}

 

---

마지막으로 이중 배열을 이용해 풀었다.

 

combi 배열을 생성할 때, k가 1인 경우 아래줄에서(21번째줄) combi[1][1]에 대입할 때 오류가 뜬다.

따라서 [N+1][K+2]의 크기로 생성해주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[][] combi = new int[N + 1][K + 2];
		combi[0][0] = combi[1][1] = combi[1][0] = 1;

		for (int i = 2; i <= N; i++) {
			for (int j = 0; j <= K && j <= i; j++) {
				if (j == 0) {
					combi[i][j] = 1;
				} else {
					combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % 10007;
				}
			}
		}

		bw.write(combi[N][K] + "");

		bw.flush();
		bw.close();
		br.close();
	}
}

---

참조

https://www.secmem.org/blog/2019/12/14/fast-binomial-calculation/

이항계수의 빠른 계산

https://eloquence-developers.tistory.com/52

[BOJ 11051번] 이항 계수 2(JAVA)