[메모이제이션] 조합의 경우의 수

설명

로 계산합니다.

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

입력

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

출력

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

예시 입력 1 

5 3

예시 출력 1

10

예시 입력 2 

33 19

예시 출력 2

818809200

 

 

 내 풀이

간단한 계산만 하기 때문에 n값이 커지면 실행에 시간이 걸린다

import java.util.Scanner;


public class Main {



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


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


        System.out.print(dfs(n,r));


    }

}

 

 

다른 풀이 - 메모이제이션

구한 값을 메모이제이션하여

즉, 이차원배열에 값을  저장해서 값이 있으면 바로 리턴받아 계산

import java.util.Scanner;


public class Main {
    static int[][] dy  =new int[34][34];//n최대 33


    public static 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  T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();


        System.out.print(dfs(n,r));


    }

}