[백준] 11050_이항계수1

 

Bronze

 

문제

 

입력

첫째 줄에 N 과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N )

 

---

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        int num = factorial(N)/(factorial(K)*factorial(N-K));
        
        System.out.println(num);

        sc.close();
        
    }
    
    public static int factorial(int n){
        if(n == 0) return 1;
        return n * factorial(n-1);
    }
}

 

 

 

---

 

이항계수

• 주어진 크기의 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 수를 의미한다.
• 전체집합 원소의 개수 n에 대해 k개의 아이템을 뽑은 이항계수를 아래와 같이 정의할 수 있다. 

 

이항계수의 성질

1. 대칭성 

n개의 원소 중 k개를 선택하는 방법과 n-k(선택받지 못한 수)를 선택하는 방법이 동일하다 

 

2. 경계조건

n개의 원소 중에서 아무것도 선택하지 않거나 모두 선택하는 경우의 수가 1이다. 

 

3. 재귀적관계

파스칼의 삼각형과 관련이 있다.

각 이항계수는 바로 위 두 이항계수의 합으로 표현될 수 있다. 

 

 

이항계수의 계산 방법

1. 팩토리얼 사용 - 큰 수를 구할 경우 오버플로우 발생 가능

public class BinomialCoefficient {
    public static long factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static long binomialCoefficient(int n, int k) {
        return factorial(n) / (factorial(k) * factorial(n - k));
    }

    public static void main(String[] args) {
        int n = 5, k = 2;
        System.out.println(binomialCoefficient(n, k));
    }
}

 

 

2. 동적 프로그래밍 (DP) - 파스칼의 삼각형 사용

public class BinomialCoefficientDP {
    public static int binomialCoefficient(int n, int k) {
        int[][] C = new int[n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            // Math.min(i, k)은 불필요한 부분을 채우지 않기 위함
            for (int j = 0; j <= Math.min(i, k); j++) {
                if (j == 0 || j == i) {
                    C[i][j] = 1;
                } else {
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
                }
            }
        }

        return C[n][k];
    }

    public static void main(String[] args) {
        int n = 5, k = 2;
        System.out.println(binomialCoefficient(n, k));
    }
}

 

 

3. 메모이제이션 사용 - 이미 계산된 값을 저장해 두고 필요할 때 다시 사용하는 기법

public class BinomialCoefficientMemoization {
    private static Map<String, Long> memo = new HashMap<>();

    public static long binomialCoefficient(int n, int k) {
        if (k == 0 || k == n) {
            return 1;
        }

        String key = n + "," + k;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        long result = binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
        memo.put(key, result);

        return result;
    }

    public static void main(String[] args) {
        int n = 5, k = 2;
        System.out.println(binomialCoefficient(n, k));
    }
}

 

---

https://www.acmicpc.net/problem/11050