[백준] 2407번 - 조합 (Silver 4)

문제 링크

백준 2407번 - 조합 (Silver 4)

문제 설명

이항계수 $n \choose m$을 계산하는 문제이다. n, m의 범위가 100까지이므로, 매우 큰 수를 처리해야한다.

정답 코드 및 설명

$n \choose m$ = ${n-1} \choose {m-1}$ + ${n-1} \choose {m}$을 이용한 DP를 수행하였다.
나올 수 있는 최댓값은 $100 \choose 50$인데, int는 물론이고 long으로도 어림도 없다.
이에 문자열 덧셈을 직접 구현하여 사용하였다.

나중에 다른 사람 답안을 보면서 알게 된 사실인데, java.math 패키지에 BigInteger 클래스가 있었다.
이를 활용한다면 훨씬 편하게 풀 수 있을 것이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        bw.write(combination(n, m));
        bw.close();
    }

    static String combination(int n, int m) {
        String comb[][] = new String[n + 1][m + 1];
        comb[0][0] = "1";
        for (int j = 1; j <= m; j++)
            comb[0][j] = "0";
        for (int i = 1; i <= n; i++) {
            comb[i][0] = "1";
            for (int j = 1; j <= m; j++) {
                comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);
            }
        }
        return comb[n][m];
    }

    static String add(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len = len1;
        if (len2 > len1)
            len = len2;

        int num1[] = new int[len];
        int num2[] = new int[len];
        int numAdd[] = new int[len + 1];
        int carry = 0;

        // 숫자 문자열을 역순으로 배열에 저장(1의 자리부터 연산을 수행하기 때문)
        for (int i = 0; i < len; i++) {
            if (i < len1)
                num1[i] = s1.charAt(len1 - i - 1) - '0';
            if (i < len2)
                num2[i] = s2.charAt(len2 - i - 1) - '0';
        }
        // 덧셈 수행(0번 인덱스가 1의 자리이다)
        for (int i = 0; i < len; i++) {
            numAdd[i] = num1[i] + num2[i] + carry;
            carry = numAdd[i] / 10;
            numAdd[i] %= 10;
        }
        numAdd[len] = carry;
        // 결과(인덱스의 역순으로 출력해야함에 주의)
        String add = "";
        for (int i = len; i >= 0; i--) {
            if (i == len && numAdd[i] == 0)
                continue;
            add += numAdd[i];
        }
        return add;
    }
}