[Ch.08 - DFS] 09. 조합의 경우수(메모이제이션)

7. 조합의 경우수(메모이제이션)

 

설명

로 계산합니다.

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

입력

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

출력

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

예시 입력 1 

5 3

예시 출력 1

10

예시 입력 2 

33 19

예시 출력 2

818809200

---

 

순서 없이 5개중 3개를 뽑는다. 5C3 [n=5, r=3]

-> 한 개를 기준으로 정해, 5가 포함된 3명, 5가 포함되지 않은 3명

=4C2 + 4C3

 

즉, nCr이 r=0이거나, n==r이 되면 종료

---

import java.util.Scanner;

//조합의 경우수 (메모이제이션)
class Main {
	int[][] dy=new int[35][35];

	public int DFS(int L, int S) {
		if (dy[L][S] > 0) {
			return dy[L][S];
		}
		if (L == S ||S == 0) {
			//S가 바뀌면서 L과 같아지거나 0이되면 1이 된다.
			return 1;
		} else {

			return dy[L][S] = DFS(L - 1, S - 1) + DFS(L - 1, S);

		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int r = kb.nextInt();
		System.out.println(T.DFS(n, r));
		

	}

}

 

 

import java.util.Scanner;

//조합의 경우수 (메모이제이션)
//nCr = n-1Cr-1 + n-1Cr
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);
			//n,r에 저장후 리턴
		}
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int r=kb.nextInt();
		System.out.println(T.DFS(n, r));
	}

}