백준 2407번 : 조합 java

이번 문제는 주어진 입력에 따른 조합의 결과를 출력하는 것입니다.

저는 보통 조합문제를 풀 때 nCm이라는 식이 주어져 있으면 n!/(n-m)!*m! 이러한 식을 이용하여 문제를 바로 해결합니다.

이 문제에서도 이러한 방식을 통해서 문제를 해결하려 하였으나 long의 범위를 넘어서기 때문에 제한이 있었습니다.

따라서 저는 이 문제의 유형이 다이나믹 프로그래밍인 것을 확인하고 파스칼의 삼각형을 사용하여 이 문제를 해결하려 하였으나 파스칼의 삼각형을 사용하더라도 long의 범위를 넘는 수가 있어 문제를 해결할 수 없었습니다.

따라서 저는 이 long의 범위를 넘어서서 수를 표기할 수 있는 방법이 자바에 있는지 찾아보았습니다.

찾아보니 java.math.BigInteger라는 class를 이용하면 long의 범위 이상을 표현할 수 있다는 것을 알게 되었습니다.

다음과 같이 오라클에서 제공해주는 자바 api에 들어가서 이 class를 확인하였습니다.

위에 적혀 있는 내용과 같이 이 class를 이용하면 무한의 수까지 표현할 수 있다고 합니다.

https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html

BigInteger (Java Platform SE 8 )

위에는 이 api에 대한 정보입니다.

이제 이 api를 이용하여 문제를 풀어보도록 하겠습니다.

---

import java.io.*;
import java.math.BigInteger;

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

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        BigInteger sum = BigInteger.ONE;
        BigInteger div = BigInteger.ONE;

        for(int i = 0; i<m; i++) {
            sum = sum.multiply(new BigInteger(String.valueOf(n-i)));
            div = div.multiply(new BigInteger(String.valueOf(i+1)));
        }

        System.out.println(sum.divide(div));
    }
}

첫번째 코드는 평소 주로 쓴다고 말씀드렸던 식인 n!/(n-m)!*m! 을 그저 단순히 대입해서 계산한 코드입니다.

무한대까지 표현이 가능하다고한 만큼 이 코드를 사용해도 백준에서는 정답처리가 되었습니다.

하지만 이 문제는 다이나믹 프로그래밍 파트에 들어가 있는 만큼 파스칼의 삼각형을 이용해서도 문제를 풀어보기로 하였습니다.

출처 : 위키백과

파스칼의 삼각형은 위의 모양과 같이 한 항의 좌측 대각선 위의 수와 우측 대각선 위의 수를 합해서 만든 삼각형입니다.

우리는 nCm의 값을 알려면 파스칼의 삼각형을 bi 배열이라고 했을 때 bi[n][m]의 값을 가져오기만 하면 됩니다.

이를 코드로 표현하겠습니다.

import java.io.*;
import java.math.BigInteger;

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

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        BigInteger[][] bi = new BigInteger[101][101];

        for(int i = 1; i<=n; i++){
            for(int j = 0; j<=i; j++){

                if(j==0||j == i)
                    bi[i][j] = BigInteger.ONE;
                else{
                    bi[i][j] = bi[i-1][j].add(bi[i-1][j-1]);
                }
            }
        }

        System.out.println(bi[n][m]);
    }
}

다음과 같이 조합문제를 해결할 수 있습니다.