[JAVA/2004번] 조합 0의 개수

문제

입력 및 출력

풀이

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

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 사용자로부터 숫자 두 개를 입력받는다.
        String[] strArray = br.readLine().split(" ");

        // N, M
        int N = Integer.parseInt(strArray[0]);
        int M = Integer.parseInt(strArray[1]);

        // nPm
        BigInteger nPmResult = new BigInteger(strArray[0]);
        int minus = Integer.parseInt(strArray[0]);
        for (int i = N; i > (N - M + 1); i--) {
            minus = minus - 1;
            nPmResult = nPmResult.multiply(BigInteger.valueOf(minus));
        }

        // m!
        BigInteger mResult = new BigInteger("1");
        for (int i = M; i > 0; i--) {
            mResult = mResult.multiply(BigInteger.valueOf(i));
        }

        // nCm
        BigInteger nCmResult = nPmResult.divide(mResult);

        int count = 0;
        String nCm = nCmResult.toString();
        for (int i = nCm.length() - 1; i >= 0; i--) {
            if (nCm.charAt(i) == '0') {
                count++;
            } else {
                break;
            }
        }
        System.out.println(count);
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법
1) 계승(팩토리얼, factorial)

• 해설: 1 부터 어떤 양의 정수 n까지를 곱한 것
• 표기법: n!
• 예: 6! = 1 x 2 x 3 x 4 x 5 x 6

2) 수열(퍼뮤테이션, permutation)

• 해설: n 의 수를 m 까지 n - 1 씩하여 곱한 것
• 표기법: nPm
• 예: 45 P6 = 45 x 44 x 43 x 42 x 41 x 40

3) 조합(콤비네이션, combination)

• 해설: 순서를 따지지 않은 숫자의 집합
• 표기법: nCm
• 예: nCm = nPm÷ m! (45 C6 = 45 P6÷ 6!)