[인프런] 08_07 조합수(메모이제이션)

📖  문제

---

• 아래의 공식을 사용하고 재귀를 이용해 조합의 수를 구해주는 프로그램을 작성하세요

조합의 경우수

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

출력 화면

⚠️  주의사항

---

• 위의 공식을 이용할 것
• 시간초과에 주의

 

✍️  이해

---

/**
 * 1. 조합수를 구하는 공식
 * 2. 입력 값 받아오기
 * 3. 2차원 배열에 공식의 값 저장하기
 * 4. DFS 반복 중 배열의 값이 0보다 크면 return 배열
 * 5. N과 R이 같거나 R이 0이면 return 1;
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int N, R;
    static int[][] answer = new int[40][40];

    public int DFS(int N, int R) {

        if(answer[N][R] > 0) return answer[N][R];
        if(N == R || R == 0) return 1;
        else return answer[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);
        N = sc.nextInt();
        R = sc.nextInt();

        System.out.println(T.DFS(N, R));
    }
}

---