[백준] 2407번 - 조합

 

public class p2407 {

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

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = b;
        long sum = 1;

        if (b * 2 < a) {
            b = a - b;
        }

        for (int i = 0; i < c; i++) {
            sum *= a;
            a--;
        }
        for (int i = 0; i < c; i++) {
            sum /= b;
            b--;
        }

        System.out.println(sum);
    }
}

가장 단순하게 생각해서 만든 코드이다. 그냥 입력받은 수들을 그대로 반복문을 이용해서 결과를 도출하도록 해주었다.

결과는 당연히 실패로 나왔고, 재귀 또는 점화식을 이용한 dp로 문제를 풀어야 할 것 같다고 생각했다.

$$ _nC_m = _{n-1}C_{m-1} + _{n-1}C_m $$ 이라는 식은 다들 학창시절에 배웠다.

 

이 수식을 이용해서 재귀함수를 만들어 문제를 풀어보았다.

 

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

public class p2407 {

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

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(combination(a, b));
    }

    public static int combination(int a, int b) {
        if (a == b || b == 0) {
            return 1;
        }
        return combination(a - 1, b - 1) + combination(a - 1, b);
    }
}

 

이 방식대로 풀면 컴파일할때도 속도가 굉장히 느린 것을 알 수 있다. 예상했듯이, 시간초과가 발생한다.

 

마지막 방법은 이 방법에서 조금 개선된 방식이다. n * m 짜리 이차원 배열을 하나 만들어서 계산한 값들을 해당 배열에 저장하는 방법이다. 또한 long형으로 배열을 선언했었는데, long형으로 했을 때 문제가 생겨 큰 수들을 사용할 때 쓰는 BigInteger를 사용했다. BigInteger에 대한 사용방법은 아래 링크를 참고하면 된다.

 

https://ddamdoo.tistory.com/197

자바 BigInteger

 

최종 작성한 소스코드이다.

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

public class p2407 {
    static BigInteger[][] ary;

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

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        ary = new BigInteger[101][101];
        combination(a, b);

        System.out.println(ary[a][b]);
    }

    public static void combination(int a, int b) {
        for (int i = 1; i <= a; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || i == j) {
                    ary[i][j] = new BigInteger("1");
                } else {
                    ary[i][j] = ary[i - 1][j - 1].add(ary[i - 1][j]);
                }
            }
        }
    }
}