[Algorithm]알고리즘 자바_60 조합의 경우 수(메모이제이션)

 

💬 문제 설명

조합의 경우 수는 위의 공식으로 계산됩니다.

하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

 

🔨 입출력 예

 

입력 - 첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

예시 입력 1)

5 3

예시 입력 2)

33 19

 

출력 - 첫째 줄에 조합수를 출력합니다.

예시 출력 1)

10

예시 출력 2)

818809200

 

 

 

 

✨ 아이디어

​

 

 

💻 Solution.java

import java.util.*;

public class Main {
	int[][] dy = new int [35][35];
	
	public int DFS(int n, int r) {
		if(dy[n][r] != 0 ) return dy[n][r];
		if(n == r || r == 0) return 1;
		else return dy[n][r] = DFS (n - 1, r - 1) + DFS(n - 1, r);
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int r = sc.nextInt();
		
		System.out.println(main.DFS(n, r));
		sc.close();
		return ;
	}
}