[ 백준 1010번 문제 ] 다리 놓기 - JAVA

이번 글에서는 백준 110번 문제를 통해 이항계수를 활용하고
최대 값을 넘어서는 순간을 다루는 방법을 알아보자.

문제 핵심

• 서쪽 ( N )
• 동쪽 ( M )
• N <= M
• 최대 한 개의 다리만 연결

풀이 과정

이 문제는 조합론으로 mCn이라고 할 수 있다.

다만 M의 최대값이 30일 때 factorial의 값은 다음과 같다.

 

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120
• 6! = 720
• 7! = 5040
• 8! = 40,320
• 9! = 362,880
• 10! = 3,628,800
• 11! = 39,916,800
• 12! = 479,001,600
• 13! = 6,227,020,800
• 14! = 87,178,291,200
• 15! = 1,307,674,368,000
• 16! = 20,922,789,888,000
• 17! = 355,687,428,096,000
• 18! = 6,402,373,705,728,000
• 19! = 121,645,100,408,832,000
• 20! = 2,432,902,008,176,640,000
• 21! = 51,090,942,171,709,440,000
• 22! = 1,124,000,727,777,607,680,000
• 23! = 25,852,016,738,884,976,640,000
• 24! = 620,448,401,733,239,439,360,000
• 25! = 15,511,210,043,330,985,984,000,000
• 26! = 403,291,461,126,605,635,584,000,000
• 27! = 10,888,869,450,418,352,160,768,000,000
• 28! = 304,888,344,611,713,860,501,504,000,000
• 29! = 8,841,761,993,739,701,954,543,616,000,000
• 30! = 265,252,859,812,191,058,636,308,480,000,000

한계는 이미 초과했다.

이 때 우리는 각 프로그래밍언어에서 제공하는 클래스를 사용하면 된다.

Java에서는 BigInteger가 있다.

 

핵심 코드

이항 계수1 문제 처럼 나왔지만 이번에는 동쪽이 숫자가 항상 크다.

( 값을 받을 때 반대로 받았다. 헷갈리지 않게 N M으로 선언하는게 좋다. )

int T = Integer.parseInt(bufferedReader.readLine());
int N, K;
BigInteger result;

for (int i = 0; i < T; i++) {
    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    K = Integer.parseInt(stringTokenizer.nextToken());
    N = Integer.parseInt(stringTokenizer.nextToken());


    result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
    stringBuilder.append(result).append("\n");
}

 

 

이번 문제는 자료형의 최대값을 한참 넘어서기 때문에,
그 부분만 해결할 수 있다면 이전 이항계수 문제를 활용해 아주 쉽게 풀 수 있는 문제이다.

꼭 BigInteger같은 클래스를 사용하지 않더라도 비슷한 방식으로
직접 문자로 만들어서 처리하는 방법도 존재한다.

 

전체코드

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

public class Main {

    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();

        int T = Integer.parseInt(bufferedReader.readLine());
        int N, K;
        BigInteger result;

        for (int i = 0; i < T; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            K = Integer.parseInt(stringTokenizer.nextToken());
            N = Integer.parseInt(stringTokenizer.nextToken());


            result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
            stringBuilder.append(result).append("\n");
        }

        System.out.println(stringBuilder);
    }
}