[백준 1676] 팩토리얼 0의 개수
백준 1676번 - 팩토리얼 0의 개수
❓ 문제
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
출력
첫째 줄에 구한 0의 개수를 출력한다.
✏️ 풀이
처음 접근
1부터 수를 계속 증가하면서 곱함.
곱한 수 % 10 == 0이라면, number /= 10 , count++
이런식으로 최대한 뒤에 0의 개수를 구하면서 정답을 구하려고 했다.
중요한건 이 방법이 작은 수 (대략 60이었나?)까지 먹히고 input으로 100을 넣었을 때 먹히지 않았다.
🔥 참고
input:100일 때의 팩토리얼 수
933262154439441526816992388562667004907159682643816214685929
638952175999932299156089414639761565182862536979208272237582
51185210916864000000000000000000000000
input이 500까지 있음을 고려하자면, 처음 접근 방식으로는 도저히 풀 수 없다.
너무 큰 수가 되기 때문.
두번째 접근
따라서 다른 방법으로 접근해야했고, 소인수 분해라는 방법이 있다는 것을 알게되었다.
뒤에 0이 붙기 위해서는 2x5의 연산이 일어나야 하므로, input을 소인수분해 하여 2x5의 연산이 얼마나 일어나는지 보면 된다.
예를 들어 input = 5라 가정하자.
factorial(5)를 구한 뒤, 0이 몇개인지 세면 된다.
factorial(5) = 1 x 2 x 3 x 4 x 5 = 120 이다.
-> 2x5가 1세트 나오므로 0의 개수는 1개
두 번만 더 해보겠다.
input = 10
factorial(10) = 1 x 2 x … x 10 = 3,628,800
-> 2x5가 2세트 나오므로 0의 개수는 2개
input = 15
factorial(15) = 1 x 2 x … x 15 = 1,307,674,368,000
-> 2x5가 3세트 나오므로 0의 개수는 3개
이렇게 수를 늘려보면 감이 온다.
2x5를 단순히 세는 것이 아니라, 5의 개수를 세면 된다.(2는 굉장히 많이 등장하기 때문에 고려를 하지 않아도 된다)
실제로 0~4 구간 : count=0
5~9 구간 : count=1
10~14 구간 : count=2
15~19 구간 : count=3 이런식으로 5의 배수일 때 count가 증가한다.
하지만 여기서 특수 case가 존재한다.
25(5^2), 125(5^3)는 5가 2번, 3번씩 등장하는 수 이다.
따라서 25가 등장할 때는, 평소보다 1번 더 카운트를 해주어야한다.
125 역시 평소보다 한번 더 카운트를 해주어야 한다.
💡 평소보다 1번 더 카운트하는 이유?
아래 코드에서 보면 알겠지만, 5로 나눈 몫을 먼저 취하기 때문에, 모든 수에서 5를 한 번 가져가게 된다.
25나 125같은 5의 제곱수는 5를 한 번 빼앗겨도 5가 남아있기 때문에 순차적으로 처리를 해주는 것이다.
아래는 이해를 돕기 위한 예시이다.
ex) input : 7
7/5 = 1
count = 1
ex) input : 25
25/5 = 5
25/25 = 1
count = 5 + 1 = 6
ex) input : 76
76/5 = 15
76/25 = 3
count = 15 + 3 = 18
ex) input : 125
125/5 = 25
125/25 = 5
125/125 = 1
count = 25 + 5 + 1 = 31
이러한 특징을 잘 캐치한다면 쉽게 풀 수 있는 문제였다.
하지만 난 특징을 캐치하지 못했으므로 쉽진 않았다.
✔️ 정답 코드
#include <iostream>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, count=0;
cin >> n;
count += n / 5;
count += n / 25;
count += n / 125;
cout << count;
return 0;
}
Leave a comment