조합의 경우의 수(재귀, 메모이제이션)

문제설명

입력 설명

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

출력 설명

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

입력예제1

33 19

출력예제1

818809200

---

메모이제이션 X 코드

import java.util.Scanner;

public class Main_8_7 {
    static int n;
    static int r;

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

    public static void main(String[] args) {
        Main_8_7 t = new Main_8_7();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        r = kb.nextInt();
        
        System.out.println(t.dfs(n,r));

    }
}

• 순열 nCr에서 만약 r==0이거나(ex: 3C0, 4C0...) n==r(3C3, 4C4...)이면 값이 무조건 1이 나오기 때문에 if를 통해 처리해주었다.
• else에서는 위 문제에서 주어진 공식을 토대로 작성하였다.
  
  

메모이제이션 활용 코드

package 코테인강.Main_8;

import java.util.Scanner;

public class Main_8_7 {
    static int n;
    static int r;
    static int[][] arr;

    int dfs(int n, int r){
        if(arr[n][r] > 0)
            return arr[n][r];
        if(r==0 || n == r)
            return 1;
        else{
            return arr[n][r] = dfs(n- 1, r-1) + dfs(n-1, r);
        }
    }

    public static void main(String[] args) {
        Main_8_7 t = new Main_8_7();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        r = kb.nextInt();
        arr = new int[35][35];

        System.out.println(t.dfs(n,r));

    }
}

• 메모이제이션을 통해 어떠한 값을 구할 때 이미 구해놓은 값이 있으면 더 이상 재귀를 뻗지 않고 구해놓은 값을 가져온다.

ex)
5C3 = 4C2 + 4C3
4C2 = 3C1 + 3C2
4C3 = 3C2 + 3C3

• 5C3을 구하려 재귀함수를 호출하다 보면 위 3C2처럼 구해놓은 값을 또 필요로 한 경우가 있다.
• 이 경우 3C2부터 다시 재귀함수를 호출하는 것이 아닌 이전에 구해놓은 3C2의 값을 불러오면 된다.

• int[][] arr 선언하여 nCr에 값을 arr에 저장해 놓는다.
• arr는 처음에 전부 0으로 초기화 되어있기 때문에 if(arr[n][r] >0)다는 것은 이전의 값을 구해 저장해 놓았다는 의미이므로 해당 값을 불러와서 사용하면 된다.

알게된 점

• 메모이제이션을 통해 구해놓은 값을 저장해 다음에 해당 값이 필요할 때 이용하여 효율성을 높일 수 있다는 것을 알게되었다.