[BaekJoon] 1010 다리 놓기

1.  문제 링크

2.  문제

요약

• 서쪽의 사이트 n개에서 동쪽에 있는 사이트 m개에 다리를 연결하는데, 이 때 다리끼리 서로 겹쳐지지 않고 n개의 다리를 지을 수 있는 경우의 수를 구합니다.(n은 m보다 작거나 같습니다)
• 입력: 첫번째 줄에는 테스트 케이스의 개수가 주어지고 그 다음 줄부터는 n과 m이 주어집니다.
• 출력: 테스트 케이스의 순서에 맞게 경우의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public int combination(int n, int m) {
		int m_temp = m;
		long m_mul = 1;
		long n_mul = 1;
		for(int i = 1; i <= n; i++) {
			m_mul *= m_temp;
			n_mul *= i;
			m_temp--;
		}
		return (int)(m_mul / n_mul);
	}
	public int calculateNum(int n, int m) {
		if(n == m) {
			return 1;
		}
		if(n > (m / 2)) {
			int dif = m - n;
			return combination(dif, m);
		} else {
			return combination(n, m);
		}
	}
	
	public ArrayList<Integer> putBridge(ArrayList<ArrayList<Integer>> testcase) {
		ArrayList<Integer> numBridge = new ArrayList<Integer>();
		for(int i = 0; i < testcase.size(); i++) {
			numBridge.add(calculateNum(testcase.get(i).get(0), testcase.get(i).get(1)));
		}
		return numBridge;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<Integer>> testcase = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < num; i++) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			String site = br.readLine();
			StringTokenizer st = new StringTokenizer(site);
			temp.add(Integer.parseInt(st.nextToken()));
			temp.add(Integer.parseInt(st.nextToken()));
			testcase.add(temp);
		}
		Main m = new Main();
		ArrayList<Integer> numBridge = m.putBridge(testcase);
		for(int i = 0; i < numBridge.size(); i++) {
			System.out.println(numBridge.get(i));
		}
	}
}

4.  접근

• 다리끼리 겹쳐지지 않도록 총 n개의 다리를 연결하는 경우의 수를 구하는 문제인데, 이는 후보군 m개에서 n개를 뽑는 경우를 구하는 문제이므로 조합을 이용하여 풀이합니다. 다리가 겹쳐지는 문제는 m개에서 n개를 뽑은 후, 서로 겹쳐지지 않도록 다리를 연결하면 되기 때문에 해결할 수 있습니다.
• 조합의 경우 nCr = nC(n-r)이 성립하므로 계산의 시간 단축을 위해 n/2보다 r이 큰 경우에는 n에서 r을 빼서 계산을 진행합니다.

• 조합은 위의 공식을 만족하기 때문에 가장 오른쪽에 있는 수식을 이용하여 조합의 코드를 구성하였습니다.
• 이렇게 조합으로 구한 결과들을 테스트케이스 순서에 맞게 출력합니다.