[백준] 2407. 조합

단, n <=r,

d [n][r] = combi(d, n - 1, r - 1) + combi(d, n - 1, r); 순서 바꾸면 안 됨

n과 m의 범위가 100 정도만 돼도 long형의 범위를 벗어난다.

ex) 90C56 = 7077867820068919738609890, 100C50 = 100891344545564193334812497256

    public static int combi(int[][] d, int n, int r) {
        if (d[n][r] != 0) return d[n][r];
        if (n == r || r == 0) return 1;
        d[n][r] = combi(d, n - 1, r - 1) + combi(d, n - 1, r);
        return d[n][r];
    }

 

BigInteger를 사용하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    static BigInteger combi(BigInteger[][] c, int n, int m) {
        if (c[n][m] != BigInteger.ZERO) return c[n][m];
        if (n == m || m == 0) return BigInteger.ONE;
        c[n][m] = combi(c, n - 1, m - 1).add(combi(c, n - 1, m));
        return c[n][m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        BigInteger[][] c = new BigInteger[101][101];
        for (BigInteger[] b : c)
            Arrays.fill(b, BigInteger.ZERO);

        System.out.println(combi(c, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));

        br.close();
    }
}