문제

1010 - 다리 놓기

문제 설명

서쪽에 𝑁개의 사이트, 동쪽에 𝑀개의 사이트가 있다.
서쪽의 사이트를 동쪽의 사이트에 1:1로 연결할 수 있는 경우의 수를 구하는 문제
단, 사이트끼리는 교차되면 안 되므로, 조합에서 순서 없이 선택하는 경우와 동일합니다.

문제 풀이 방법

팩토리얼 연산을 할 수 있는 함수를 만들어 계산
입력이 최대 30이기 때문에, int 범위 내에서 계산 가능

코드

package silver5;

import java.io.*;
import java.util.*;

public class Main {
	
	static int combination(int n, int r) {
        if (r == 0 || n == r) return 1;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            sb.append(combination(M, N)).append("\n");
        }

        System.out.print(sb);
    }
}

코드 설명

1. factorial 함수:

   • 1부터 n까지 곱해서 팩토리얼 계산

2. combination 함수:

   • 𝑀개 중 𝑁개 고르는 조합 계산

3. 입력 처리:

   • 첫 줄에 테스트 케이스 수 T
   • 이후 T개의 줄에 각각 N, M 입력받고 조합 계산 후 출력