조합 (Combination) nCr

여기서 !는 팩토리얼을 의미합니다. 예를 들어, 5!은 5 4 3 2 1입니다.

Java에서 nCr 계산하기
nCr을 계산하기 위해 팩토리얼을 구하는 함수와 이를 이용한 조합 계산 함수를 작성할 수 있습니다. 다음은 Java에서 이를 구현한 예제입니다:

public class Combination {

    // 동적 프로그래밍을 사용한 조합 계산 함수
    public static long nCr(int n, int r) {
        if (r > n) {
            return 0;
        }
        if (r == 0 || r == n) {
            return 1;
        }

        long[][] dp = new long[n + 1][r + 1];

        // 초기값 설정
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= r; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        return dp[n][r];
    }

    public static void main(String[] args) {
        int n = 5;
        int r = 3;
        System.out.println("C(" + n + ", " + r + ") = " + nCr(n, r));
    }
}