조합수 (메모이제이션)

설명

로 계산합니다.

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

 

입력

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

 

출력

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

 

예시 입력 1 

5 3

 

예시 출력 1

10

 

예시 입력 2 

33 19

 

예시 출력 2

818809200

 

 

문제 해결

 

조합을 계산하는 문제이다.

조합에서 C(n,r)=1인 경우는n==r 또는 r==0인 경우이고, 그 외의 경우에는 조합의  C(n−1,r−1)과 C(n−1,r)의 합을 반환해 재귀를 이용하며 ㅣ용해주면 된다.

 

 

 

최종 코드

 

import java.util.Scanner;

public class P07_조합수_메모이제이션 {

    static int n, r;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        r = in.nextInt();

        System.out.println(Combination(n,r));
    }

    public static int Combination (int n, int r) {
        if (n == r || r == 0) return 1;
        else return Combination(n-1, r-1) + Combination(n-1, r);
    }
}