메모

/*
사이트 = 주변에서 다리를 짓기에 적합한 곳을 
	N = 서쪽 사이트 (N ≤ M)
    M = 동쪽 사이트

조건 1 : 한 사이트에는 최대 한 개의 다리만 연결 가능
조건 2 : 서쪽의 사이트 개수만큼 (N개) 다리를 짓기
조건 3 : 다리끼리는 서로 겹쳐질 수 없다

다리를 지을 수 있는 경우의 수?
*/

---

해결법

방법 1

import java.util.Scanner;
 
public class Main {
	
	static int[][] dp = new int[30][30];
 
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
        
		for (int i = 0; i < T; i++) {
			
			// M개중 N개를 뽑는 경우 = nCr 에서 n = M, r = N
			int N = in.nextInt();		// N = r
			int M = in.nextInt();		// M = n
						
			sb.append(combi(M, N)).append('\n');
		}

		System.out.println(sb);
	}
	
	static int combi(int n, int r) {
		
		// 경우 1 : 경우의 수가 바로 나올 경우, 그대로 반환
		if (dp[n][r] > 0) {
			return dp[n][r]; 
		}
		
		// 경우 2 : nC₀ = 1 일 경우
		if (n == r || r == 0) {
			return dp[n][r] = 1;
		}
		
		// 경우 3 : n과 r의 이항계수 구할 경우
		return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
	}
}

• 참고: 조합 공식 + 파스칼 삼각형

• 유사한 문제

  참고: 이항 계수 1 (백준 11050번)

---

참고: [백준] 1010번 : 다리 놓기 - JAVA [자바]

---

다리 놓기 (백준 1010번)