[Java] 백준알고리즘 #1010 다리 놓기

백준알고리즘 #1010 다리 놓기 문제

서쪽의 사이트 n 개와 동쪽의 사이트 m개를 이을 다리를 놓을 때, 이 다리를 놓는 경우의 수를 구하는 문제이다.

 

구하는 방법은 간단하다. m개의 사이트에서 n개를 고르는 경우의 수는 m Combination n (mCn) 으로 해결할 수 있다.

이를 구하는 공식은

백준알고리즘 #1010 다리 놓기 문제

서쪽의 사이트 n 개와 동쪽의 사이트 m개를 이을 다리를 놓을 때, 이 다리를 놓는 경우의 수를 구하는 문제이다.

 

 

 

구하는 방법은 간단하다. m개의 사이트에서 n개를 고르는 경우의 수는 m Combination n (mCn) 으로 해결할 수 있다.

 

이를 구하는 공식은 다음과 같다

출처 : 네이버 지식백과 (경우의 수 공식모음)

다만 위 식을 조금 간단히 하면 코드도 간단히 해결할 수 있다.

n이 r보다 크므로 n!은 n x (n-1) x ... x r x (r-1) x ... x 2 x 1 로 볼 수 있으므로

이를 약분하면 n x (n-1) x ... x (r+1) 이 분모가 된다.

즉 분자는 n부터 r개의 수를 차례로 곱한 것이고, 분모는 r부터 1까지를 차례로 곱한 것이라 볼 수 있다.

 

이를 코드로 나타내면 다음과 같다.

for (int j = 0; j < r; j++) {
	result = result * (n - j) / (j + 1);
}

j 가 r 까지 증가하면서 n - j  즉 n - 0 , n -1 .... 을 r번만큼 곱해주고

마찬가지로 분모에도 j + 1 즉 1, 2, 3 ... 을 r번만큼 곱해주면 된다.

이때 result는 곱셈이므로 1로 초기화해준다.

 

전체 코드를 보면 다음과 같다.

 

import java.util.Scanner;

public class Back1010 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();
		int result;
		for (int i = 0; i < t; i++) {

			int n = sc.nextInt();
			int m = sc.nextInt();

			result = 1;
			for (int j = 0; j < n; j++) {
				result = result * (m - j) / (j + 1);
			}
			System.out.println(result);

		}
	}

}