백준 3474번 [교수가 된 현우](C++) -yes6686- 티스토리

백준 문제 풀이: 3474 [교수가 된 현우]

---

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

문제 설명:

팩토리얼 n!의 뒤에 붙는 0의 개수를 구하는 문제입니다. 이 값은 10의 소인수 분해에서 2와 5의 쌍에 의해 결정되며, 2의 개수는 항상 5보다 많기 때문에 5의 개수만 계산하면 됩니다.

---

문제 해결 코드

// 백준 3474 - 교수가 된 현우
#include <iostream>
using namespace std;

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

    int T;
    cin >> T; // 테스트 케이스 개수 입력

    while (T--) {
        int n;
        cin >> n; // 입력된 수 n
        int cnt = 0; // 0의 개수를 저장할 변수

        // 5의 배수로 나누며 5의 개수를 센다
        for (int k = 5; k <= n; k *= 5) {
            cnt += (n / k);
        }

        cout << cnt << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 팩토리얼에서 뒤에 붙는 0의 개수는 소인수 5의 개수에 의해 결정됩니다.
  • n을 5의 배수로 나누며, 각 단계에서 포함된 5의 개수를 누적합니다.
• 구현 세부사항:
  • 초기값 k = 5에서 시작해, k를 5씩 곱하면서 5의 거듭제곱을 확인합니다.
  • 만약 k > n이 되면 반복을 종료합니다.
• 시간 복잡도 분석:
  • 5의 거듭제곱을 반복문으로 확인하므로 O(log₅(n))입니다.
  • 테스트 케이스가 T개이므로 총 시간 복잡도는 O(T ⋅ log₅(n))입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!