[BOJ 2004] 조합 0의 개수

2004번: 조합 0의 개수

문제 분석

• 제한 시간 2초 : Big-O기준 약 2억 연산
• 입력되는 정수 최댓값 : 20억
• 수행시간 O(n) 불가, 최대한 연산을 줄여야 한다.
• 20억의 수가 들어올 수 있으므로 변수의 메모리를 넉넉하게 long long 으로 할당한다.
• nCr : n!/(r!(m-r)!)
• 뒷 자리에 0이 생기려면 10이 곱해져야 한다.(10 = 2 x 5)

풀이 방식

• n부터 n보다 작은 수 중에 2ⁱ 의 배수의 개수를 센다.( i 는 1부터 2ⁱ ≤ n) --- f2(n)
• n부터 n보다 작은 수 중에 5ⁱ 의 배수의 개수를 센다.( i 는 1부터 5ⁱ ≤ n) --- f5(n)
• m, n-m 도 똑같이 진행해준다.
• f2(n) - (f2(m) + f2(n-m)) 와 f5(n) - (f5(m) + f5(n-m)) 를 비교해 더 작은 값을 출력한다.

f2(x), f5(x) 구하기

• x부터 x보다 작은 모든 수에 대해 하나하나 배수의 개수를 세는 방식은 시간초과가 날 것이 뻔하다.
• f2(x)를 구할 때, 먼저 2의 배수의 개수를 구해준다. -> ⎣x/2⎦
  그리고 i를 증가 시키며 2ⁱ의 배수의 개수를 구한다.
  2ⁱ의 배수의 개수를 더해간다.
• 원리 :
  1. 1부터 어떤 수 A 까지 2의 배수(짝수)의 개수를 구하는 법 -> ⎣A/2⎦
  2. 1단계에서 소인수로 2를 하나이상 갖는 수는 셋다.
  3. 2를 소인수로 두개이상 갖는 수는 2² (= 4) 로 나눠주어 세면 된다.
  4. 위와 같은 방식으로 2ⁱ 배수의 개수를 더해가며 f2(n)을 구한다.
• f5(x)도 같은 방식으로 구한다.

#include <iostream>

using namespace std;

long long int n, m, result;

long long int fTwo(long long int x) {
    long long int cnt = 0;
    for (long long int i = 2; i <= x; i *= 2) { // 2ˣ의 배수의 개수를 센다
        cnt += x / i;
    }
    return cnt;
}

long long int fFive(long long int x) {
    long long int cnt = 0;
    for (long long int i = 5; i <= x; i *= 5) { // 5ˣ의 배수의 개수를 센다
        cnt += x / i;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    fTwo(n) - fTwo(m) - fTwo(n - m) < fFive(n) - fFive(m) - fFive(n - m) ?
            result = fTwo(n) - fTwo(m) - fTwo(n - m) :
            result = fFive(n) - fFive(m) - fFive(n - m);

    cout << result << "\n";
    return 0;
}

느낀점

• x부터 x보다 작은 모든 수에 대해 하나하나 배수의 개수를 세는 방식으로 풀었다. 당연히 값은 제대로 나오지만 시간초과가 떴다.
• 2ⁱ의 배수의 갯수를 세는 방법을 구현 하며 2의 배수의 갯수부터 세보다가 짝수의 갯수를 세고 있다는 생각이 들었다.
• 처음엔 한 수에 2는 몇개고 4는 몇개고 2ⁱ는 몇갠지 셌었는데 짝수의 갯수를 세는 방법을 떠올리고는 문제를 빠르게 풀어냈다.
• 처음에 IDE 부터 켜서 풀다가 고민을 오래해보고 푸니 금방 풀었다. ( 제발 고민좀 오래하고, 시간복잡도 계산 해보고 풀자!!!!)

시간 복잡도

• result 구하기 : O(1)
• f2 : O(log₂n) -> O(logn)
• f5 : O(log₅n) -> O(logn)
  ➣O(logn)