백준 11050 이항 계수 1 Java 풀이

문제

n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다.

n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 다음과 같이 정의한다. = 'nCk = n!/(n-k)!k!'

제약사항: 1 <= n <= 10, 0 <= k <= n

접근

n!/(n-k)!k! 를 구현해내면 된다.

조합의 정의를 이용

팩토리얼은 그 계산이 단순하여 DP 로 구현이 가능하고, n! 과 (n-k)!k! 의 값을 DP 로 풀어내면 될 것이다.

N 의 크기가 최대 10으로 제한되어 있으므로 Heap Memoy OOM 걱정은 없고, n!, (n-k)!, k! 를 계산할때 이미 계산했던 데이터를 이용하므로 속도상 이점이 있을 것이다.

시간복잡도

팩토리얼 계산을 해야하므로 O((N)) 의 시간복잡도를 가질 것이다.

 

이항계수의 정의를 이용

조합의 정의를 이용해서 팩토리얼을 구현하여 푸는 방법은 나쁜 풀이는 아닌것 같다. 하지만 너무 직관적이다.

통계, 수학과 관련된 문제는 그 성질을 파악하는게 중요하므로 싶어서 이항계수의 성질을 찾아보았다.

 

그 결과 간단한 2개의 성질을 알게 되었다.

[정의 1] n 개중에 n 개를 고르는 경우와 n 개중 0개를 고르는 경우는 1이다.

[정의2] n 개중에서 k 개를 뽑아내는 방법은 'n-1 개중 k 개를 뽑아내는 방법' 과 'n-1 개중 k-1 개를 뽑아내는 방법'의 개수의 합과 같다. 다시 정리하면 i 개의 아이템 중 j 개의 아이템을 선택하는 경우의 수는 그보다 작은 두 값의 합이다.

 

출처: 잘 정리된 블로그

 

 

이상의 성질을 이용하여 n 개중  k 개를 고르는 이항계수를 잘개 쪼개서 DP 로 조합이 가능해진다.

이런식으로 풀어진다.

Step1. [정의 1]을 이용하여 DP 를 초기화한다.

Step2. [정의 2]를 이용하여 n 과 k 를 순회하면서 DP 에 이항계수 값을 채워나간다.

시간복잡도

n 번, 그리고 k 번 순회를 하므로 O((n* k)) 의 시간복잡도를 가질 것이다.

풀이

조합의 정의를 이용

import java.util.Scanner;

public class Main {
    private static final int[] CACHE = new int[11];
    public static void main(String[] args) {
        CACHE[0] = 1;
        CACHE[1] = 1;
        CACHE[2] = 2;
        CACHE[3] = 6;
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(factorial(N) / (factorial(N-K) * factorial(K)));
    }

    private static int factorial(int num) {
        if(CACHE[num] != 0) {
            return CACHE[num];
        }
        CACHE[num] = (CACHE[num-1] == 0 ? factorial(num-1) : CACHE[num-1]) * num;
        return CACHE[num];
    }
}

이항계수의 정의를 이용

import java.util.Scanner;

public class Main {
    private final static int SIZE = 10;
    private final static int[][] CACHE = new int[SIZE+1][SIZE+1];

    public static void main(String[] args) {
        // 이항계수 정의 1번을 이용해 초기화 한다.
        for (int i = 0; i < SIZE+1; i++) {
            CACHE[i][0] = 1;
            CACHE[i][i] = 1;
        }
        Scanner sc = new Scanner(System.in);
        System.out.println(binomialCoefficient(sc.nextInt(), sc.nextInt()));
    }

    private static int binomialCoefficient(int n, int k) {
        // 이항계수 정의 2번을 이용해 i, j 를 점진적으로 증가시키면서 계산한다.
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < k+1; j++) {
                CACHE[i][j] = CACHE[i-1][j] + CACHE[i-1][j-1];
            }
        }

        return CACHE[n][k];
    }
}

 

결과 비교

적어도 문제 11050 에서는 두 풀이방법의 시간 결과가 똑같다.