백준(BOJ) 2004 : 조합 0의 개수 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

이 문제를 풀기 위해서는, 일단 고등학교 때 수학 시간에 배웠던 조합에 대한 기억을 되살려야한다. 많은 걸 기억해낼 필요는 없고, 밑에 있는 공식 하나만 기억하면 된다.

조합의 값 끝자리 0의 개수를 구하기 위해서는, 조합의 값을 소인수분해 했을 때 10 (2 X 5)을 얼마나 많이 가지고 있는지를 구하면 된다. 예를 들면, 50은 5 X 10이니까 0이 한 개이다. 342000은 342 X 10 X 10 X 10이니까 0이 세 개이다.

 

당연히 조합값을 다 구한 다음에 계산하는 것은 불가능에 가깝다. n, m의 최대값이 int의 최대값에 가까운 상황에서 팩토리얼 계산이 들어가버리면... 아무리 큰 자료형을 쓴다고 해도 그것들을 다 담아내는 것은 거의 불가능할 것이다. 어차피 우리가 궁금한 것은 조합값 자체가 아니라 조합값을 소인수분해했을 때 포함되어있는 2와 5의 개수이다.

 

팩토리얼 계산에 들어가는 값들을 일일히 소인수분해하여 2와 5의 개수를 셀 수도 있을 것이다. 필자는 처음에 그렇게 생각하고 풀었으나... 시간초과가 떴다...ㅠㅠ 시간초과로 실패한 필자의 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        long twoCnt = 0;
        long fiveCnt = 0;
        
        twoCnt = getCnt(n, 2) - getCnt(m, 2) - getCnt(n - m, 2);
        fiveCnt = getCnt(n, 5) - getCnt(m, 5) - getCnt(n - m, 5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
    }
 
    private static long getCnt(int n, int a) {
        long cnt = 0;
        
        for(int i = a; i <= n; i += a) {
            int temp = i;
            
            while(temp != 0 && temp % a == 0) {
                cnt++;
                temp /= a;
            }
        }
        
        return cnt;
    }
}

 

시간초과가 뜨자 위의 코드를 여러 방식으로 바꾸어 보았다. 한 번의 연산에서 2와 5를 모두 계산하고, 조합 자체의 수학 공식을 변형하여 더 적은 연산횟수로 바꿔보기도 했으나, 일일히 소인수분해를 해서 개수를 확인한다는 컨셉 내에서는 결국 시간초과를 벗어날 수 없었다. 결국 구글링 ㄱㄱ...ㅠㅠ

 

이제 구글링을 통해 풀어낸 풀이에 대한 설명을 하겠다. 소인수분해를 통해 2와 5의 개수를 구한다는 기본컨셉은 동일하다. 근데 그 개수를 구하는 방식에 차이가 있다.

 

59!을 소인수 분해했을 때 5가 몇 개 있는지를 구하는 과정을 예를 들어 설명해보겠다.

59! = 59 X 58 X 57 X 56 X ..... X 2 X 1

즉, 1 ~ 59 수의 곱이다. 그렇다면 이 중 5의 배수는 몇 개일까? 59 / 5 = 11개이다. 11개 이 외의 수들은 체크해볼 필요도 없이 5를 소인수로 포함하고 있지 않을 것이다. 11개의 수를 나열해보면, 55 X 50 X 45 ... 10 X 5 이다. 59!은 최소한 11개의 5를 소인수로 가지고 있는 것이다. 11개의 5는 이제 카운트 되었으니, 각각의 11개의 수들을 5로 나눠보면,

11 X 10 X 9 X ... X 2 X 1 이 된다. 여기에서 5의 배수의 개수는 11 /5 = 2개가 된다. 이런 방식을 통해, 59!을 소인수분해했을 때 5는 총 13개가 있다는 것을 알 수 있다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int twoCnt = get(n, 2) - get(m, 2) - get(n - m, 2);
        int fiveCnt = get(n, 5) - get(m, 5) - get(n - m, 5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
    }
    
    private static int get(int n, int k) {
        int cnt = 0;
        
        while(n >= k) {
            cnt += n / k;
            n /= k;
        }
        
        return cnt;
    }
}

 

위와 같은 방식으로 소인수의 개수를 구할 수 있다는 아이디어를 떠올리는 것이 어렵다... 유레카!하고 떠오르면 좋겠다만 천재가 아닌 이상 그게 쉽진 않을 것 같다. 결국 이런 풀이의 경우 외우고 있는 것이 좋을 것 같다는 생각이 든다.