백준 1010번 다리 놓기 [고등수학 조합] :: 마이구미

이번 글은 백준 알고리즘 사이트 1010번 다리놓기에 대해 알아볼 것이다.

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

M개 중 N개의 다리를 놓는 경우의 수를 구하는 문제다.

경우의 수하면 많은 공식들이 있다.

고등학생 때 배웠을 것이다.

다시 슬쩍 보면 기억날 것이라 생각한다.

조합에 대해 살짝 언급하겠다.

nCr, 엔씨알 익숙할 것이다.

서로 다른 n개에서 순서를 생각하지 않고 r개를 뽑는 것을 n개에서 r개를 택하는 것을 의미

조합의 공식은 n! / r!(n-r)! 이다.

깊은 내용은 다른 글을 참고하길 바란다.

본인이 학창시절에 배운 방식으로 문제를 해결해보겠다.

예로 n =5, r = 3 일 경우를 보자.

n은 r갯수만큼 -1씩 해서 곱한다. r은 3이니 5,4,3이 되겠다.

그리고 r!을 나눈다.

5 * 4 * 3 / 3 * 2 * 1 = 10

항상 이런 식으로 풀었던 기억이 나서 이번에도 이것을 활용했다.

for문 2개면 끝이다.

쉬운 코드로써, 충분히 분석 가능하리라 생각한다.

하나 설명하자면,

자바의 BigInteger을 사용했다.

정말 큰 수가 필요할 때 유용하게 자바에서 제공해주는 녀석이다.

쓰는 이유는 이전 글을 참고하자. (1834번 나머지와 몫이 같은 수)

아래는 전체 소스이다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        
        for (int i = 0; i < num; i++) {
            int r = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(combination(r,n));
        }
 
    }
    public static BigInteger combination(int r, int n)
    {
    	BigInteger sum = new BigInteger("1");
    	int temp = r;
    	
    	while(r > 0) {
    		sum = sum.multiply(BigInteger.valueOf(n));
    		--r;
    		--n;
    	}
    	
    	while(temp > 0) {
    		sum = sum.divide(BigInteger.valueOf(temp));
    		--temp;
    	}
    	
        return sum;
    }
}