[BaekJoon/백준] 2004번

어렵다. 수학적인 사고를 요하는 문제다.

 

이전 1676번 (팩토리얼 0의 개수 구하기)과 유사한 문제지만, 이번 문제는 숫자 최대범위가 20억이여서 해당 풀이 방식을 쓰면 시간초과가 난다. 다른 방법이 필요했다.

 

사람들의 풀이를 봤다. 처음에 이해가 안됐는데, 정말 잘 정리해주신 분의 글을 참고했다.

 

ksj14.tistory.com/entry/BackJoon1676-팩토리얼-0의-개수

[BaekJoon][1676] 팩토리얼 0의 개수

물론 1676번에 관한 풀이지만, 2004번에서도 쓸 수 있는 풀이다. 첫 번째로 설명해 주신 풀이가 내가 1676번을 풀었던 풀이이고,

두 번째로 설명해주신 풀이가 첫 번째 풀이로는 불가능한 2004번을 위해 필요한 풀이다. 

 

이분보다 설명을 잘 할 순 없을 것 같아서..링크만 첨부했습니다.

 

 

2, 5를 약수로 갖는 수들을 모두 찾아내는 방식의 풀이로, 뭔가 풀이하면서 약간 에라토스테네스의 체 느낌이 물씬 들었다.

#include <stdio.h>
#define MIN(a,b) ((a<=b)?a:b)

long long N, K;
long long arr[2];


long long two(long long a) {
    long long result = 0;
    
    for(long long i = 2; i <= a; i *= 2) {
        
        result += a / i;
    }
    return result;
}

long long five(long long a) {
    long long result = 0;
    
    for(long long i = 5; i <= a; i *= 5) {
        
        result += a / i;
    }
    return result;
}
int main() {
    
    scanf("%lld %lld", &N, &K);
    
    //nCr = n! / ((n - k)! * k!)
    
    arr[0] = two(N) - two(N - K) - two(K);
    arr[1] = five(N) - five(N - K) - five(K);
    
    printf("%lld", MIN(arr[0], arr[1]));
    
    
}

이 풀이에 동적계획법을 합성해볼 수 없을까 생각해봤는데, 점화식 세우는게 불가능에 가까워 보여서 포기..