문제링크

풀이

동쪽 M개의 사이트에서 n개를 고르면 된다.
중복이 있으면 안되고, 순서를 고려하지 않고 뽑는 것이므로 조합에 해당한다.

조합의 공식은 다음과 같다.
$nCr$ = $n!\over n!(n-r)!$
$nCr$ = $(n-1)C(r-1) + (n-1)Cr$

코드

package BOJ;

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

public class sol1010 {
    static int t, n, m;
    static int[][] dp;

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

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            dp = new int[30][30];
            System.out.println(factorial(m, n));
        }

    }

    static int factorial(int n, int r) {
        if (dp[n][r] > 0) { //  이미 계산된 값이면 그 값을 반환
            return dp[n][r];
        }
        if (n == r || r == 0) { //  nC0 = 1, nCn = 1
            return dp[n][r] = 1;
        }
        return dp[n][r] = factorial(n - 1, r - 1) + factorial(n - 1, r);
    }

}