백준 11051 이항 계수 2 Java 풀이

문제

n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다. 결과값을 10007 로 나눈 나머지를 출력한다.

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

 

출처: https://www.acmicpc.net/problem/11051

접근

이항 계수1 풀이와 마찬가지로 조합의 정의를 이용한 접근, 그리고  이항계수의 정의를 이용한 접근 모두 사용해볼 수 있겠다.

하지만 조합의 정의를 이용했을 경우에는 모듈러 연산이 복잡해지므로 이 단계에서는 간단한 모듈러 정의만 이용하기 위해 이항계수의 정의를 이용한 풀이만 소개한다.

모듈러 연산의 특징 을 고려해서 코드를 약간 변형해줘야한다.

모듈러 연산의 특징

• 덧셈에 대한 모듈러: (a+b) %  m =((a % m) + (b %  m)) %  m
• 곱셈에 대한 모듈러: (a*b) %  m =((a % m) * (b %  m)) %  m

 

다음 글인 이항 계수 3 풀이에서는 페르마 소정리에 의한 풀이가 강제되므로 조금 더 어려운 모듈러 연산을 이용해보자

풀이

이항계수의 정의와 모듈러 연산의 특징을 이용

import java.util.Scanner;

public class Main {
    private final static int SIZE = 1000;
    private final static int MOD = 10007;
    private final static long[][] CACHE = new long[SIZE+1][SIZE+1];

    public static void main(String[] args) {
        for (int i = 0; i <= SIZE; i++) {
            CACHE[i][0] = 1;
            CACHE[i][i] = 1;
        }

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(binomialCoefficient(n, k));
    }

    private static long binomialCoefficient(int n, int k) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                CACHE[i][j] = (CACHE[i-1][j] + CACHE[i-1][j-1]) % MOD;
            }
        }
        return CACHE[n][k];
    }
}

 

CACHE[i][j] 는 i 개중에 j 개를 추출하는 이항계수의 값이고 이 값은 이항계수의 정의, 'n 개중에서 k 개를 뽑아내는 방법은 'n-1 개중 k 개를 뽑아내는 방법' 과 'n-1 개중 k-1 개를 뽑아내는 방법'의 개수의 합과 같다.' 에 의해 계산된다.

 

이러한 각 계산값에 모듈러 연산을 해주는 과정에서 각각의 CACHE[i-1][j] 와 CACHE[i-1][j-1]는 이미 내재적으로 모듈러 연산이 되어있는 상태로 보기 때문에 그들을 % MOD 해주는 것으로 자연스럽게 덧셈에 대한 모듈러 연산 조건을 충족하게 된다.

CACHE[i][j] = (CACHE[i-1][j] + CACHE[i-1][j-1]) % MOD;