113. 1010 (다리놓기)

import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		while(T!=0) {
			String[] sBits = br.readLine().split(" ");
			BigInteger N = BigInteger.valueOf(Integer.parseInt(sBits[0]));
			int A = Integer.parseInt(sBits[0]);
			BigInteger M = BigInteger.valueOf(Integer.parseInt(sBits[1]));
			int B = Integer.parseInt(sBits[1]);
			
			if (A == 0) {
				System.out.println(1);
			} else {
				for (int i = 1; i < A; i++) {
					N = N.multiply(BigInteger.valueOf(A - i));
					M = M.multiply(BigInteger.valueOf(B - i));
				}
									
				BigInteger bigNum = M.divide(N);
				sb.append(bigNum + "\n");				
			}
			T--;
		}
		System.out.print(sb);
	}
}

문제요약

이항계수를 구하라. (조합)

설명

이항계수를 푸는방법은 위와같이 반복문이 아닌 재귀함수를 사용해서도 풀 수 있다.

 

일단 위 방법은 예를들어 10 과 5가 들어왔다고 해보자.

n은 N으로, r은 K로 생각하면 된다.

다음과 같이 값이 들어올 것이다.

이를 정리하면,

다음과 같이 나올 것이다.

즉, N과 K는 K번 1씩 감소하고 둘을 나누면 된다.

 

만약, K가 0이라면,

다음과 같으므로 1이 나오게 된다.

 

그러나

int를 사용하게 된다면 범위를 벗어나게 된다.

따라서 무한대를 표시할 수 있는 BigInteger를 사용했다.

https://smhope.tistory.com/297?category=1052317 

[Java] BigInteger