[실전 문제] combinationzero

1. 문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.

 

nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 1 * 2 * 3 * 4 * 5)

 

n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.  

---

입력

첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다.

출력

첫째 줄에 0의 개수를 출력한다.

예제 입력

25 12

예제 출력

2

 

 

 

2. 풀이

이 문제는 끝자리의 0의 개수를 직접 계산하는 방법으로 하면 시간 초과 문제가 발생한다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        long result = pascal(n, m);

        int count = 0;
        while(true) {
            if(result % 10 == 0) {
                result /= 10;
                count++;
            }
            else break;
        }
        bw.write( count + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static long pascal(long n, long m) {
        // 5C2
        // = 4C2 + 4C1
        // = 3C2 + 3C1 + 4C1
        // = 2C2 + 2C1 + 3C1 + 4C1

        if(n == m || m == 0) return 1;
        if(m == 1) return n;

        return pascal(n-1, m) + pascal(n-1, m-1);
    }

}

따라서, 직접 계산하는 방식이 아닌, 10이 되는 2와 5의 개수를 찾아내는 것이 가장 핵심이다. 단, 수식에 따라 개수를 찾아야한다.

• n!/m!(n-m)! 

 

package org.example;

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int count2 = 0;
        int count5 = 0;
        for(int i = 2; i <= n; i++) {
            int num = i;
            while(num % 2 == 0 || num % 5 == 0) {
                if(num % 2 == 0) {
                    count2++;
                    num /= 2;
                } else if(num % 5 == 0) {
                    count5++;
                    num /= 5;
                }
            }
        }

        for(int i = 2; i <= m; i++) {
            int num = i;
            while(num % 2 == 0 || num % 5 == 0) {
                if(num % 2 == 0) {
                    count2--;
                    num /= 2;
                } else if(num % 5 == 0) {
                    count5--;
                    num /= 5;
                }
            }
        }

        for(int i = 2; i <= n-m; i++) {
            int num = i;
            while(num % 2 == 0 || num % 5 == 0) {
                if(num % 2 == 0) {
                    count2--;
                    num /= 2;
                } else if(num % 5 == 0) {
                    count5--;
                    num /= 5;
                }
            }
        }

        bw.write(Math.min(count2, count5) + "");

        br.close();
        bw.flush();
        bw.close();
    }

}