[#70][알고리즘] 팩토리얼 0의 개수
백준 > 팩토리얼 0의 개수
문제 링크(https://www.acmicpc.net/problem/1676)문제
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
출력
첫째 줄에 구한 0의 개수를 출력한다.
예제 입력 1
10
예제 출력 1
2
#include <iostream>
using namespace std;
int main() {
int i, n, temp, five = 0, two = 0;
cin >> n;
for ( i = 2; i <= n; i *= 2) {
two += n / i;
}
for (i = 5; i <= n; i *= 5) {
five += n / i;
}
int answer = (five > two ? two : five);
cout << answer;
return 0;
}
| cs |
=> 2와 5의 개수 중 작은 수
예) n = 8일 때 팩토리얼 값(40320)
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
= 1 * 2 * 3 * (2 * 2) * 5 * (2 * 3) * 7 * (2 * 2 * 2)
= (2^7) * (3^2) * (5^1) * 7
= (10^1) * (2^6) * (3^2) * 7
= 4032 * (10^1)
첫 번째 for문
i = 2 : two = 0 + 8/2 = 4
i = 4 : two = 4 + 8/4 = 6
i = 8 : two = 6 + 8/8 = 7
두 번째 for문
i = 5 : five = 0 + 8/5 = 1
=> two = 7, five = 1
0의 개수 1개.
예) n = 10일 때 팩토리얼 값 (3628800)
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
= 1 * 2 * 3 * (2 * 2) * 5 * (2 * 3) * 7 * (2 * 2 * 2) * (3 * 3) * (2 * 5)
= (2^8) * (3^4) * (5^2) * 7
= (10^2) * (2^6) * (3^4) * 7
= 36288 * (10^2)
첫 번째 for문
i = 2 : two = 0 + 10/2 = 5
i = 4 : two = 5 + 10/4 = 7
i = 8 : two = 7 + 10/8 = 8
두 번째 for문
i = 5 : five = 0 + 10/5 = 2
=> two = 8, five = 2
0의 개수 2개.
댓글
댓글 쓰기