조합의 경우의 수

27 May 2023 in Algorithm on Java, Coding, Test

문제

설명

로 계산합니다.

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

입력

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

출력

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

예시 입력 1

5 3

예시 출력 1

10

예시 입력 2

33 19

예시 출력 2

818809200

해결방법

• 현재 함수의 값은 하위 2개의 리턴 값과 같다는 것을 기본으로 함.
• 2차원 배열로 특정 값일 때(n == m, m == 0) 1이 고정 이므로 배열에 넣고 체크한다.
• return chk[n][m] = 1; 구문에서 chk[n][m]은 2차원 배열에서 n번째 행과 m번째 열에 해당하는 원소를 나타냅니다. 그리고 = 연산자는 대입 연산자로, 오른쪽 피연산자인 1을 왼쪽 피연산자인 chk[n][m]에 대입하고, 그 결과인 1을 반환합니다. 따라서, return chk[n][m] = 1; 구문은 chk[n][m] 에 1을 대입하고, 1을 반환하는 것을 의미합니다. 이 구문은 동시에 chk[n][m]이 1임을 나타내는 데도 사용될 수 있습니다. 예를 들어, chk[n][m]이 1이면 이미 해당 지점을 방문한 것으로 간주할 수 있습니다.

코드

import java.util.*;

class Main {
    // 조합 수 계산할 배열
    int[][] dy = new int[35][35];

    public int DFS(int n, int r) {
        // 0보다 크다면 해당 값을 리턴한다.
        if (dy[n][r] > 0) return dy[n][r];
        // 0인 경우 1을 리턴한다.
        if (n == r || r == 0) return 1;
        // DFS 계산을 통해 두 조합의 값을 더해 대입 후, 리턴한다.
        else return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
    }

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