Java로 nCr(조합)을 계산하는 프로그램 작성 방법

이 글에서는 n과 r 값을 이용해 조합(nCr)을 계산하는 방법을 자세히 알아봅니다. nCr은 서로 다른 n개의 항목 중에서 순서에 상관없이 r개를 선택하는 경우의 수를 의미하며, 다음 공식으로 계산할 수 있습니다.

nCr = (n의 팩토리얼) / (r의 팩토리얼 × (n-r)의 팩토리얼)

즉, n! / (r! × (n−r)!) 형태로 표현됩니다. 여기서 팩토리얼(factorial)은 1부터 해당 수까지의 모든 정수를 곱한 값으로, 예를 들어 5! = 5 × 4 × 3 × 2 × 1 = 120입니다.

다음은 실제 동작 예시입니다.

입력

입력값이 다음과 같다고 가정해 보겠습니다.

n의 값 : 6
r의 값 : 4

출력

기대되는 출력 결과는 다음과 같습니다.

nCr 값 : 15

알고리즘

단계 1 - 시작
단계 2 - 정수형 변수 n과 r을 선언한다.
단계 3 - 사용자로부터 필요한 값을 입력받거나 값을 미리 정의한다.
단계 4 - 두 개의 함수를 정의한다. 하나는 n과 (n-r)의 팩토리얼을 계산하는 함수이며,
다른 하나는 공식인 (n의 팩토리얼) / (r의 팩토리얼 × (n-r)의 팩토리얼)을 계산해 결과를 저장하는 함수이다.
단계 5 - 결과를 화면에 출력한다.
단계 6 - 종료

예제 1: 사용자 입력을 받는 경우

이 예제에서는 Scanner 객체를 사용해 사용자가 직접 n과 r 값을 입력하면 그에 맞는 조합 값이 출력됩니다. 온라인 코딩 환경에서 직접 실행해 보면서 동작을 확인할 수도 있습니다.

import java.util.*;
public class Combination {
   static int Compute_nCr(int n, int r){
      return my_factorial(n) / (my_factorial(r) *
      my_factorial(n - r));
   }
   static int my_factorial(int n){
      int i, my_result;
      my_result = 1;
      for (i = 2; i <= n; i++)
         my_result = my_result * i;
      return my_result;
   }
   public static void main(String[] args){
      int n,r;
      System.out.println("Required packages have been imported");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter the value of n : ");
      n = my_scanner.nextInt();
      System.out.print("Enter the value of r : ");
      r = my_scanner.nextInt();
      System.out.println("The combination value for the given input is = "+Compute_nCr(n, r));
   }
}

출력

Required packages have been imported
A reader object has been defined 
Enter the value of n : 6
Enter the value of r : 4
The combination value for the given input is = 15

예제 2: 값이 미리 정의된 경우

이번에는 n과 r 값이 코드 안에 미리 정의되어 있으며, 프로그램 실행 시 해당 값을 사용해 결과를 콘솔에 바로 출력합니다.

public class Combination {
   static int Compute_nCr(int n, int r){
      return my_factorial(n) / (my_factorial(r) *
      my_factorial(n - r));
   }
   static int my_factorial(int n){
      int i, my_result;
      my_result = 1;
      for (i = 2; i <= n; i++)
         my_result = my_result * i;
      return my_result;
   }
   public static void main(String[] args){
      int n,r;
      n = 6 ;
      r = 4 ;
      System.out.println("The n and r values are defined as " +n + " and " +r);
      System.out.println("The combination value for the given input is = "+Compute_nCr(n, r));
   }
}

출력

The n and r values are defined as 6 and 4
The combination value for the given input is = 15

코드 설명

위 코드에서 Compute_nCr 메서드는 nCr 공식을 그대로 구현한 것으로, n!, r!, (n−r)! 세 팩토리얼 값을 이용해 최종 조합 값을 반환합니다. my_factorial 메서드는 반복문(for 루프)을 사용해 팩토리얼을 계산하며, 초기값을 1로 설정한 뒤 2부터 n까지 차례로 곱해 나가는 방식입니다. 이처럼 팩토리얼 계산 로직과 조합 계산 로직을 분리해두면 코드의 가독성과 재사용성이 크게 향상됩니다.