1010. 다리 놓기 (자바, Java)

이항계수(조합) 문제다. M개중에 N개만큼 골라주는 경우의 수를 따지는 것이기 때문.

크기가 충분히 클 것 같아 BigInteger로 풀었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());		
		StringBuilder sb = new StringBuilder();
		
		for (int i=0; i<t; i++) {		
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		sb.append(bc(m,n) + "\n");
		
		}
		
		System.out.println(sb);
	}
	
	static BigInteger bc(int n, int k) {
		
		BigInteger npk = new BigInteger("1"); // nPk 순열
		
		for (int i=n; i>n-k; i--) {
			npk = npk.multiply(BigInteger.valueOf(i));
		}
		
		BigInteger kf = new BigInteger("1"); // !k 팩토리얼
		
		for (int i=k; i>1; i--) {
			kf = kf.multiply(BigInteger.valueOf(i));
		}
		
		return npk.divide(kf);
	}

}