문제
알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!
그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.
그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.
그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.
그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).
출력
각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.
예제
문제 정의
이 문제는 예시를 끄적여보며 원리를 파악하는게 중요하다 (큰돌님 해설 참고)
예를 들어, 2400이라는 숫자가 있을 때 24x10x10으로 이루어져있다.
이를 보면 맨 오른쪽끝의 0의 개수를 파악하기 위해선 10의 개수를 파악하면 된다. 10은 2와 5를 곱해서 이루어져있으므로 2와 5로 나누어 떨어지는 횟수를 세면 된다.
이때 조건에서 n이 10억 이하 이므로 모든 경우의 수를 돌려가며 개수를 더하면 시간초과가 난다.
따라서 2의 배수, 5의 배수로 각각 반복문을 돌려 몫을 저장하면 된다.
2의 배수와 5의 배수의 수가 같아야 10의 배수 1개가 만들어지므로 2의 배수의 개수, 5의 배수의 개수 중 더 작은 값을 출력하면 10의 배수가 몇개 만들어지는지 알 수 있다.
코드는 다음과 같다.
#include<bits/stdc++.h>
using namespace std;
int t, a, cnt;
int main() {
cin >> t;
for (int i = 0; i < t; i++) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> a;
int res2 = 0, res5 = 0;
for (int j = 2; j <= a; j *= 2) {
res2 += a / j;
}
for (int j = 5; j <= a; j*=5) {
res5 += a / j;
}
cout << min(res2, res5) << "\n";
}
}맨 처음에,
이와 같은 코드를 쓰지 않고 로직을 써서 테스트를 돌렸더니 시간초과가 떴다. 하지만 위의 코드를 쓰고나니 시간 초과가 뜨지 않고 정답처리 되었다.
왜일까?
1. ios_base::sync_with_stdio(false)
- c++의 cin과 cout은 기본적으로 c의 scanf와 printf와 동기화되어 있다.
- 이 동기화는 c와 c++ 표준 스트림을 함께 사용할 떄의 데이터 충돌을 방지한다. 하지만 이 동기화가 불필요한 성능 손실을 유발하기도 한다.
- ios_base::sync_with_stdio(false)를 사용하면 이 동기화를 끄고, cin과 cout의 독립적인 사용을 허용하여 속도를 크게 향상시킨다.
2. cin.tie(NULL)
- 기본적으로 cin은 cout과 연결되어 있다.
- 이는 cin으로 입력 받을 때, 이전에 출력 버퍼에 남아 있는 내용을 먼저 처리하도록 강제한다.
- cin.tie(NULL)을 설정하면 이러한 연결을 끊어 cin과 cout이 독립적으로 동작할 수 있도록 한다. 이로 인해 불필요한 출력 처리 시간이 줄어든다.
3. cout.tie(NULL)
- cout의 기본 동작에 대해 추가적인 설정을 해제하여 성능을 더욱 최적화할 수 있다.
- 일반적으로 cin.tie(NULL)으로 충분하므로 cout.tie(NULL)은 필수는 아니지만, 추가로 설정하여 안전성을 확보할 수 있다.
c++의 표준 입출력은 기본적으로 느린 편이기 때문에, 많은 양의 데이터를 처리하는 경우 병목현상이 발생할 수 있다. ios_base::sync_with_stdio(false); 와 cin.tie(NULL);을 추가하면 입출력 작업의 속도가 크게 개선되어 시간초과 문제를 해결할 수 있다.
따라서 이는 많은 양의 입출력이 있는 문제를 해결할 때 유리하다.
‼️ 하지만 ios_base::sync_with_stdio(false)는 c++의 cin과 cout이 c의 scanf와 printf와 동기화하지 않도록 설정하는 것이기 때문에 cin, cout를 사용하는 도중에 scanf와 printf를 함께 사용할 경우 문제가 발생할 수 있다.
앞으로는 혹시모를 성능문제를 고려하여 위와 같은 입출력 설정을 하고 문제를 푸는 습관을 들여야겠다!
