https://www.acmicpc.net/problem/1676
시간 제한 | 메모리 제한 | solved.ac 티업 |
2초 | 128MB | 실버 4 |
문제
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
출력
첫째 줄에 구한 0의 개수를 출력한다.
단순히 팩토리얼을 계산하는 문제가 아니라, 처음 0이 아닌 숫자가 나올 떄까지의 0의 개수를 구하는 것이다. 팩토리얼은 숫자가 조금만 커져도 그 값이 엄청나게 커지기 때문에, 단순 계산으로 시도하면 당연히 오버플로우가 나게 된다.
문제에 조금 집중해보면, 처음 0이 아닌 숫자가 나올때까지의 0은, 10의 거듭제곱꼴이 곱해져 있다는 뜻이다. 10은 2 x 5로 분해되기 때문에, 결국 이 문제는 주어진 팩토리얼을 소인수 분해했을 때, 2와 5가 몇개가 있는지를 찾아야 하는 문제이다.
또한, 2와 5의 개수가 다를 수도 있는데, 그 개수가 더 적은 쪽이 당연히 답일 것이다. 2^3 * 5^2라는 숫자가 있다면, 이 숫자는 10^2 * 2이기 때문이다.
2부터 입력받은 숫자까지 반복문을 돌면서 소인수 2와 5의 개수를 세서 더 적은쪽을 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
void solution(int n) {
int cnt_2 = 0;
int cnt_5 = 0;
int temp;
for(int i = 2; i <= n; i++) {
temp = i;
while(temp % 2 == 0) {
cnt_2++;
temp /= 2;
}
while(temp % 5 == 0) {
cnt_5++;
temp /= 5;
}
}
cout << min(cnt_2, cnt_5);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
solution(n);
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2012번 C++ 풀이 (0) | 2022.03.22 |
---|---|
백준 2947번 C++ 풀이 (0) | 2022.03.22 |
백준 2729번 C++ 풀이 (0) | 2022.03.21 |
백준 2225번 C++ 풀이 (0) | 2022.03.19 |
백준 10610번 C++ 풀이 (0) | 2022.03.18 |