[Inflearn] 자바 알고리즘 문제풀이 #08-07 7. 조합의 경우수(DFS, 메모이제이션)

문제

설명

로 계산합니다.

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

 

입력 

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

 

출력 

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

 

예시 입력 1 

5 3

예시 출력 1

10

예시 입력 2 

33 19

예시 출력 2

818809200

 

 

 

내 풀이 = 선생님 풀이

import java.util.Scanner;

public class Main8_7 {
    static int[][] m;
    public int DFS(int n, int r){
        if(m[n][r]>0) return m[n][r];
        if(n==r || r==0) return 1;
        else return m[n][r] = DFS(n-1, r-1) + DFS(n-1, r);
    }

    public static void main(String[] args) {
        Main8_7 T = new Main8_7();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        m = new int[n+1][n+1];
        T.DFS(n, r);
        System.out.println(m[n][r]);
    }
}

예전에 피보나치 재귀에서 "메모이제이션"에 대한 개념을 접했기 때문에 응용해서 풀 수 있었다.

 

조합이 서로 다른 n개 중 r개를 선택하는 경우의 수를 구하는 것이니까,

if(n==r) : 서로 다른 2개 중 2개를 선택하는 경우의 수 ==> 1가지(2개 모두 뽑는다)

if(r==0) : 서로 다른 n개 중 0개를 선택하는 경우의 수 ==> 1가지(아무것도 뽑지 않는다)

 

그리고 메모이제이션 배열m에서 0보다 큰 값이 들어왔을 때 (즉, 이미 이전에 재귀호출 되어 값이 저장되어 있는 경우)

다시 계산하는 것이 아니라 해당 값을 리턴해주면서 계산 시간을 줄이는 것까지 알아두면 좋을 문제인 것 같다.

 

 

 

결과