[JAVA]백준 알고리즘 11051번 : 이항 계수 2

11051번: 이항 계수 2

문제

 

풀이

체감상 매우 어려운 문제였는데, 해결하고 보니 크게 어렵지는 않았다.

고등학교 수학 과정에서 배웠던 nCk 를 10,007로 나눈 나머지를 구하는 문제이다.(C : 조합 기호, Combination)

 

처음에 "이항 계수 1" 문제와 다른 점이 없다고 생각해서 그대로 풀고, 10,007로 나눈 나머지를 구해 보았는데 런타임 에러 (/ by zero)가 발생했다.

다시 보니 "이항 계수 1"문제과는 달리 N의 범위가 1,000 이하의 수라는 것을 알았고, 똑같은 방법에 int 대신 long을 써보았는데, 같은 오류가 발생했다.

 

찾아보니 nCk를 구하는 방법에 문제가 있었다.

나는 nPk를 k! 로 나누는 방법을 사용하였는데, 이렇게 하면 숫자가 너무 커져 long타입 변수의 범위도 넘어버린다.

결론은 nCk = (n-1)C(k-1) + (n-1)Ck 임을 이용해야 했다.(C : 조합 기호, Combination)

 

따라서 이차원 배열에 nCk의 값을 채우는 방법을 써야 하고, 이 과정에서 "동적 계획법"이라는 방법을 사용해야 한다.

동적 계획법이란, 같은 계산을 여러번 해야 하는 경우에 해당 계산의 결과를 저장해놓으면 그 계산을 한 번만 해도 된다는 것을 이용한 방법이다.

하지만 위 방법을 이용해도, 출력이 잘 되지 않았다. N의 범위가 너무 큰 탓이었다.

또 찾아보니, 모듈러 연산(%연산)의 성질을 알고 있어야 풀 수 있는 문제였다.

이 문제에서 쓰이는 모듈러 연산의 성질은 아래와 같다.

 

(a + b) % M = ((a % M) + (b % M)) % M

 

위 성질을 알고 있으면, 아무리 N의 범위가 커도 이차원 배열에는 nCk % 10,007의 값을 저장하기 때문에 10,007보다 작은 값을 저장하면서 계산을 진행할 수 있다.

 

아래 코드의 getC함수는 동적 계획법과 nCk = (n-1)C(k-1) + (n-1)Ck 성질을 이용하고, 모듈러 연산의 성질도 이용하여 이차원 배열을 채워나가는 함수이다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][K + 1];

        int result = getC(N, K);

        System.out.println(result);
    }
    public static int getC(int N, int K) {
        if(arr[N][K] != 0) return arr[N][K];

        if(N == K || K == 0) {
            arr[N][K] = 1;
        }else {
            arr[N][K] = (getC(N - 1, K - 1) + getC(N - 1, K)) % 10007;
        }

        return arr[N][K];
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!