3474 : 교수가 된 현우 - 소인수 분해, ios_base::sync_with_studio(false);cin.tie(NULL);cout.tie(NULL)

https://www.acmicpc.net/problem/3474

3474번: 교수가 된 현우

문제요약

펙토리얼 값 마지막에 0이 몇 개 등장하는지

 

난이도

Silver 3

---

풀이 포인트

• 소인수
• ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) 
  • ios_base::sync_with_stdio(false)
    • 표준 stream과의 동기화를 끊는다. cin과 cout이 scanf,prinf에 비해 속도가 느린데, 동기화를 끊어 사용하는 버퍼의 수를 줄여 실행 속도를 높일 수 있음
    • 근데 오류를 야기하기도 하나 보다.. 입출력이 제일 어렵군
  • cin.tie(NULL);cout.tie(NULL);
    • 묶여 있는 것을 풀어줌. 정확히 어떤 원리인지 깊숙히는 이해할 수 없으나 이것도 실행 속도 높이는 방법

*버퍼 : 데이터를 내보내거나 받아들이기 전에 임시로 저장하는 것.즉, 입력을 받고 버퍼에 저장했다가 다시 꺼내 쓰는 방식인데 이런 중간과정을 위 코드등을 통해 생략하는 것임.

---

REVIEW

 

오히려 이런 수학적 문제(?)는 접근이 어렵진 않다.

끝자리가 0이 나오려면 소인수 2와 5의 쌍이 있어야 한다.

소인수 2의 개수가, 5의 개수보다 확연히 많을 것이기 때문에 5의 개수만 체크해 준다.

 

다 구현해두고 시간초과가 떠서,

분할 정복이니, 구간합이니 별 걸 생각했는데 참.

 

ios::sync_with_stdio , cin.tie , cout.tie 때문에 시간초과가 났다.

앞으로 디폴트로 적어두자.

---

CODE

#include <bits/stdc++.h>
using namespace std;
// 시간초과

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;

    int fiveCnt = 0;

    for(int i = 0; i < n; i++){
        int k;
        cin >> k;

        fiveCnt = k/5;		//첫 5의 배수 카운트를 따로 해주지 않고 아래 반복에 끼워넣으면 오답이더라.. 왜인진 분석해보기

        for(int j = 25; j <=k; j*=5){
            fiveCnt += k/j;
        }

        cout << fiveCnt <<'\n';
    }
}