[내문내풀] N! 끝에서부터 0이 아닌 숫자가 등장하기 전까지 0의 갯수 구하기

내가 내고 내가 풀어보기.

 

예전, 한 기업 코딩테스트에서 비슷한 문제를 받았던 기억이 있어서 기록해두기 위해 풀어보는 문제이다.

 

숫자 N이 주어졌을 때, N! 을 계산한 결과에서 가장 오른쪽부터 0이 아닌 숫자가 등장하기 전까지의 0의 갯수를 출력하시오

입력 예시
15

출력 예시
3

입력 제한
0 <= N <= 1000

풀이
15! = 1,307,674,368,000 이며
우측에서부터 0이 아닌 수가 나오기 전까지의 0의 갯수는 3개이다.

 

단순한 알고리즘 풀이라기 보다는, 사고력을 테스트하기 위한 문제라고 생각을 했다.

실제로, N! 을 계산을 하는 것이 아닌, 원리를 찾아내는 문제.

 

우측에 0이 생기는 기준은, 곱하는 수에서 2의 갯수와 5의 갯수 중 최소값을 찾는 문제라고 생각했다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int solve_result(int N) {
	int count_2 = 0, count_5 = 0;
	while(N > 0) {
		int N_copy = N;
		
		// 2로 나눠지는 경우
		while(N_copy % 2 == 0) {
			count_2 ++;
			N_copy /= 2;
		}
		
		// 5로 나눠지는 경우
		while(N_copy % 5 == 0) {
			count_5 ++;
			N_copy /= 5;
		}
        
		N--;
	}
	int result = min(count_2, count_5);
	return result;
}

int main() {
	int N; cin >> N;
	cout << solve_result(N) << endl;
	return 0;
}

 

다 풀고 나서 생각해보니

factorial은 항상 1에서부터 모든 수를 곱해가기 때문에

모든 팩토리얼 결과에서 2의 배수보다 5의 배수가 많을 수 없다고 생각했다.

즉, 5로 나눠지는 숫자만 출력해도 정답이 되지 않을까 하는 생각을 해본다.