[BaekJoon] 백준 1010번 다리놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

다리 놓기 문제

 

다리는 중복될 수 없고 최대한 놓을 수 있는 경우의 수를 구하는 문제입니다.

 

M개의 다리중에서 중복을 제외한 N개의 다리를 선택하는 조합 문제입니다.

 

조합 특성을 사용해 재귀함수로 풀었습니다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int test_case = scan.nextInt();
		for(int j = 1; j<=test_case; j++) {
			int r = scan.nextInt();
			int n = scan.nextInt();

			
			System.out.println(func(n, r));
		}
	}
	
	public static int func(int n, int r) {
		if(r == 0 || r == n)
			return 1;
		if(r == 1)
			return n;
		
		else {
			return func(n-1, r) + func(n-1, r-1);
		}
	}
}