[백준] 1010 다리놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

이 문제는 수학적인 내용을 알면 쉽게 해결할 수 있는 문제이다. mCn이라는 것은 총 m개의 값 중에서 n개를 순서있게 선택할 때 만들수 있는 경우의 수와 같다. 다만 주의할 점은 팩토리얼 부분이 들어가있기 때문에 자료형의 범위를 신경써야하는데, 모든 범위의 표현이 가능한 BigInteger를 사용하면 해결할 수 있다.

---

문제 및 입출력

---

코드

import java.util.Scanner;
import java.math.BigInteger;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int t = sc.nextInt();
        // overflow 방지를 위한 BigInteger 자료형 선언
        BigInteger[] dp = new BigInteger[31];
        dp[1] = new BigInteger("1");
        
        for(int i=2; i<dp.length; i++)
        {
            dp[i] = new BigInteger(i+"").multiply(dp[i-1]);
        }
        
        for(int i=0; i<t; i++)
        {
            int n = sc.nextInt();
            int m = sc.nextInt();
            
            // case 1 : n==m일 때는 무조건 1
            if(n==m)
            {
                sb.append(1 + "\n");
            }
            // case 2 : mCn : m! / (n! * m-n!)
            else
            {
                sb.append(dp[m].divide(dp[n].multiply(dp[m-n])) + "\n");
            }
        }
        
        System.out.print(sb.toString());
        sc.close();
    }
}