[Algorithm/Java] 알고리즘 자바 조합의 경우의 수 DFS (코딩테스트, DFS, BFS, 조합의 개수 구하기, combination, 메모이제이션, Memoization)

---

1. 문제 설명

• 설명
  로 계산합니다.
  이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.
  
• 입력
  첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.
• 출력
  첫째 줄에 조합수를 출력합니다.

 

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

public class NumberOfCombinations {
  int[][] dy = new int[35][35]; // 먼저 계산된 조합을 저장하는 배열

  public static void main(String[] args) {
    NumberOfCombinations T = new NumberOfCombinations();
    Scanner kb = new Scanner(System.in);

    int n = kb.nextInt();
    int r = kb.nextInt();
    System.out.println(T.DFS(n, r));
  }

  public int DFS(int n, int r) {
    if (dy[n][r] > 0) return dy[n][r]; // 먼저 계산된 조합이 있다면 재귀함수를 돌리지 않고 리턴
    if (n == r || r == 0) return 1; // 가장 끝 노드에 도달했을 때, 곧 조합의 값이 1일때 리턴
    else return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r); // 주어진 공식을 사용
  }
}

 

3. 출력 예시

입력 1
5 3

출력 1
10

입력 2
33 19

출력 2
818809200

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의