[백준] 1010번 - nCr 조합 공식

>>문제 바로가기<<

두 정수가 주어졌을 때, 두 정수가 이루어질 수 있는 경우의 수가 얼마나 되는지 묻는 문제이다.

이건 대놓고 조합 공식 nCr을 묻는 문제이다.

단, 이번 문제의 경우 수가 매우 커질 수 있으므로
오버플로우 발생 가능성이 있다.
때문에 매 계산마다 곱셈과 나눗셈을 동시에 수행하는 편이 좋다.

for(int i=0; i<N; i++){
	result *= (r - i);
    result /= (i + 1);
}

위 알고리즘을 사용하면, 분자는 n부터 n-r+1까지 모두 곱하고,
r! 만큼 나눠지는 연산이 가능하다.
분자의 n!이 n-r+1까지만 연산되는 이유는 분모의 (n-r)!과 약분되기 때문이다.

위 정보를 바탕으로 설계한 코드는 다음과 같다.

import java.util.*;
import java.io.*;

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0; i<T; i++){
        	st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int result = 1;
            
            if(N == M){
            	bw.write(result + "\n");
                continue;
            }
            
            for(int j=0; j<N; j++){
            	result *= (M-j);
                result /= (j+1);
            }
            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
    }
}

맞았습니다!!