백준 1676번 [팩토리얼 0의 개수](C++)-yes6686- 티스토리

백준 문제 풀이: 1676 [팩토리얼 0의 개수]

---

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

문제 설명:

n! (n 팩토리얼)에서 끝에 붙는 0의 개수를 구하는 문제입니다. 0은 2와 5의 곱으로 만들어지므로, 팩토리얼의 소인수 분해에서 5의 개수를 세는 것이 핵심입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    int n;
    int cnt = 0;
    cin >> n;
    for (int i = 5; i <= n; i *= 5) {
        cnt += (n / i);
    }
    cout << cnt;
}

---

코드 설명

• 핵심 아이디어: 2와 5의 곱으로 0이 만들어지는데, 팩토리얼에서는 2가 항상 5보다 많으므로 5의 개수만 세면 됩니다.
• 구현 세부사항:
  • i = 5부터 시작하여, i를 5씩 곱해가며 n / i를 누적합으로 더합니다.
  • 각 단계에서 n / i는 i가 약수로 포함된 개수를 의미합니다.
• 시간 복잡도: O(log₅ n)
  • 5의 거듭제곱 수만큼 반복하므로 매우 효율적입니다.

---

결과

입력된 n!에서 끝에 붙는 0의 개수를 정확히 계산할 수 있습니다. 문제를 해결하기 위해 팩토리얼을 직접 계산하지 않고도 효율적으로 해결할 수 있습니다.

추가 질문이나 다른 접근 방식에 대한 의견이 있다면 댓글로 남겨주세요!