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

1676번: 팩토리얼 0의 개수

문제 분석

• 뒷 자리에 0이 생기려면 10이 곱해져야 한다.(10 = 2 x 5)
• n부터 n보다 작은 수 중에 2ⁱ 의 배수의 개수를 센다.( i 는 1부터 2ⁱ ≤ n 일때 까지)
• n부터 n보다 작은 수 중에 5ⁱ 의 배수의 개수를 센다.( i 는 1부터 5ⁱ ≤ n 일때 까지) 

풀이 과정

• 2ⁱ 의 배수의 개수와 5ⁱ 의 배수의 개수 를 구해 더 작은 것을 출력한다.
• 이를 구하는 방식은 2004번 문제 "조합 0의 개수"를 풀 때와 같은 논리다.
• https://genius00hwan.tistory.com/76

[BOJ 2004] 조합 0의 개수

#include <iostream>

using namespace std;

int n, cnt2, cnt5;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 2; i <= n; i *= 2) {
        cnt2 += n / i;
    }
    for (int i = 5; i <= n; i *= 5) {
        cnt5 += n / i;
    }
    cnt2 < cnt5 ? cout << cnt2 : cout << cnt5;
}

느낀 점

• 이미 풀어본 문제와 비슷한 문제를 풀때는 힐링을 하는 것 같다 ㅎㅎ ( 더 쉬운 문제라면 더더욱)
• 또, 내가 공부를 하긴 했구나 하는 뿌듯함을 느끼며 문제를 풀게된다.
• 이 문제를 풀며 2004번 문제를 풀때 써먹었던 논리를 머릿속에 확실히 넣게 된거 같다.

시간 복잡도

• 2ⁱ 의 배수의 개수 구하기 : O(log₂n) -> O(logn)
• 5ⁱ 의 배수의 개수 구하기 : O(log₅n) -> O(logn)
  ➣O(logn)