[BAEKJOON] 2004 조합 0의 개수

문제 요약

• 알고리즘 분류: 수학, 조합
• 난이도: Silver2
• 문제내용:
  • 조합 결과값에서 끝자리 0의 개수를 구해라!
• 사이트 주소: https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

문제풀이

1. 문제 접근방법

https://jih3508.tistory.com/21

[BAEJOON] 11051 이항 계수 2

https://jih3508.tistory.com/25

[BAEJOON] 1010 다리놓기

이번 문제는 조합을 사용해서 풀어야 하는데 위 2개 문제랑 푸는 방식이랑 다르다.

from math import factorial

n, m =  map(int, input().split())
result = str(factorial(n) // (factorial(n-m) * factorial(m)))
print(len(result) - len(result.rstrip('0')))

 주어진 문제 입력값이 20억까지라서 dp나 factorial처럼 완전탐색사용할 경우 시간초과가 나올것이다.

 하지만 이번 문제는 조합의 값을 구하는게 아니라 뒤에 0이 몇개 붙어 있는지 알아야 한다. 그래서 조합한 결과값을 소인수 분해 해서 2^N × 5^N = 10^ N에서 N 개수를 구하면 된다.

  일단 조합값을 소인수 분해해서 2 와 5의 개수를 구하는게 먼저 인다.  조합을 구하기 전에 factorial의 공식을 보면

  N! = (1 × 2 × 3 × 4 × 5 .... × N)이 있는데 2부터 본다면, 2로 나눠 지는 수는 N / 2 나누어서 몫이 값 만큼이 있다. 하지만 2로 나누어 떨어지는 수만 구해야 하는것이 아니라 2의 N승을 구해야 하기 때문에 2의 제곱 2의 세제곱 숫자가 2^N 미만까지 각 나누어 떨어 지는 개수를 구해서 각 경우의 수를 다 더해야 한다. 5도 마찮가지로 5^1 부터 5^N까지 나누어 떨어 지는 수를 구해서 더하면된다.

하지만 위의 조합공실을 보면 N!의 2와 5의 소인수 분해 지수값뿐만 아니라 (n-m)!, m!까지 구해야 한다.

 그래서 조합 공식을 따라서 전체적으로 2와 5의 소인수 분해한 지수 값을 구하는 식은

• count2(n) - count2(m) - count2(n-m)
• count5(n) - count5(m) - count5(n-m)

위처럼 식을 세울수가 있다. 그다음 2와 5의 지수중 가장 작은 값을 구하면 조합값의 끝자리 0의개수가 된다.

 

알고리즘

1. 2와 5의 지수를 구하기 위해서 구하는 함수를 만들어야 한다.
2. 반복문으로 n, m의 숫자이하까지 각 제곱근의 개수를 구해서 더한다.
3. n, m, n-m factorial의 2 와 5의 소인수분해한 지수 값을 구한다.
4. 결과 값을 n - m - (n-m) 이식 처럼 대입을 한다.
5. 2와 5의 소인수분해한 값중 가장 작은것을 출력한다.

Code

Python

def count2(num):
    result = 0;
    i = 2
    while( i <= num):
        result += num//i
        i *= 2
    return result

def count5(num):
    result = 0;
    i = 5
    while( i <= num):
        result += num//i
        i *= 5
    return result

n, m =  map(int, input().split())

cnt2 = count2(n) - count2(m) - count2(n-m)
cnt5 = count5(n) - count5(m) - count5(n-m)

print(min(cnt2, cnt5))

Java

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

public class Main {

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		
		long cnt2 = count2(n) - count2(m) - count2(n-m);
		long cnt5 = count5(n) - count5(m) - count5(n-m);
		
		System.out.println(Math.min(cnt2, cnt5));
		
	}
	
	public static long count2(long num) {
		long result = 0;
		
		for(long i = 2; i <= num; i *= 2) {
			result += num/i;
		}
		
		return result;
	}
	
	public static long count5(long num) {
		long result = 0;
		
		for(long i = 5; i <= num; i *= 5) {
			result += num/i;
		}
		
		return result;
	}
	
}

마무리

 실버2 문제라서 쉬울줄 알았는데 이번 문제는 조합공식에 대한 이해와 수학에 대한 지식이 없으면 풀수 문제가 아니라 그래서 이런 문제는 수학 공부를 틈틈히 해놓지 않으면 못풀수 있기 때문에 시간날때 중등수학부터해서 다시 공부하는것이 좋다고 생각난다.