[백준 2024/01/22] 1010번 다리 놓기

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

1010번: 다리 놓기

 

1. 접근 방법

이번 문제는 조합 문제 + 큰 수 처리 문제라고 할 수 있다.

강 서쪽의 사이트 개수를 기준으로 강 동쪽의 사이트들을 정하게 되면,

위에서 아래로부터 순서대로 강 서쪽의 사이트들과 연결지으면 되기 때문이다.

 

따라서 (강 동쪽의 사이트 개수)C(강 서쪽의 사이트 개수) 를 하면 된다.

 

이 경우, 11050번 조합 코드를 가져와서 사용하였다.

하지만, 문제가 있다면 해당 문제에서는 int 범위를 벗어날만큼 큰 수를 요구하기도 한다는 것이었다.

따라서 long으로 바꾸어서 계산을 시도하였지만, 해결이 되지 않았다.

 

따라서 최후의 수단인 BigInteger을 이용하였다.

BigInteger의 경우 값을 초기화 할 때도 다른 변수와는 차이점을 보였다.

 

numerator.divide(denominator);
numerator.multiply(BigInteger.valueOf(i));

 

이것처럼 곱셈, 나누셈의 경우에 메서드처럼 호출해서 사용해야 했으며,

valueOf(1)를 통해 숫자를 초기화 할 경우에도 메서드를 호출해서 넣어줘야 했다.

 

BigInteger를 사용하게 된다면 느려질 수 있다는 점에서 시간 기준을 맞추지 못할까봐 걱정하였는데,

다행히도 그러진 않았다.

 

2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Deque;
import java.util.ArrayDeque;
import java.math.BigInteger;


public class b1010 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(reader.readLine());

        for(int i = 0; i<num; i++) {
            String line = reader.readLine();
            String[] nums = line.split("\\s+");
            int r = Integer.parseInt(nums[0]);
            int n = Integer.parseInt(nums[1]);

            System.out.println(combination(n, r));

        }
    }
    public static BigInteger combination(int n, int r){
        BigInteger numerator = factorial_up(n,r);
        BigInteger denominator = factorial(r);
        return numerator.divide(denominator);
    }

    public static BigInteger factorial(int num){
        BigInteger result = BigInteger.ONE;
        for(int i = num; i >0;i--){
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static BigInteger factorial_up(int n, int r){
        BigInteger result = BigInteger.ONE;
        for(int i = n; i > n-r; i--){
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

}