[알고리즘] 백준 1010 : 다리놓기 - JAVA

문제

1010번: 다리 놓기

문제이해

강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 하고 서쪽에는 N개 동쪽에는 M개의 사이트가 있다(n <= m)

다리는 한사이트에 최대 한개만 연결될 수있고 서로 겹칠 수 없을 때 다리를 지을 수 있는 경우의 수를 모두 구하는 문제이다

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

• T 
• N M (N 과 M는 공백으로 구분되어 입력)

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다

---

풀이

 

한 사이트는 최대 한 개의 다리만 연결되는 것과 다리가 서로 겹칠 수 없는 단서를 확인한다면 조합 문제라는 것을 알 수 있습니다. 그렇다면 문제는 mCn을 구하는 문제가 되며 이는 m! 을(m-n)!n!으로 나눈 값이 된다.

---

코드

import java.util.Scanner;

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

        int test_case = sc.nextInt();

        for(int i = 0; i < test_case; i++){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int answer = 1;
            //  n == m 이면 경우의 수가 1개
            if(n == m)answer = 1;
            else{
                //  nCr 계산
                for(int j = 0; j < n; j++){
                    answer *= m-j;
                    answer /= 1+j;
                }
            }
            System.out.println(answer);
        }
    }
}