코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이

이번 문제는 정말 꼼수(?)로 푼것같다 -_-; 한마디로 수학적인 검증? 철학? 이런게 없ㅋ엉ㅋ 

일단 나의 답. 다른 사람들과 비교하니 맞는 것같다.

2012! = 501 8

10000! = 2499 8

아래 책에서 나온 문제라는 것!!

문제는 아래와 같다. (새창으로보기)

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

1. n의 범위는 1 이상, 10000 이하입니다.
2. 테스트 입력은 다음과 같습니다.
   20! = 2432902008176640000
   30! = 265252859812191058636308480000000
   40! = 815915283247897734345611269596115894272000000000
   50! = 30414093201713378043612608166064768844377641568960512000000000000
   100! = 93326215443944152681699238856266700490715968264381621468592963
   8952175999932299156089414639761565182862536979208272237582511852
   10916864000000000000000000000000
3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

저 어마어마한 숫자들을 다 저장한다는건 문제를 포기하겠다는 것이고 ..

생각해보니 0이 몇개인지를 카운트 해두고 앞에 몇자리 수만 기억해두면 될 것같았다. 

어차피 곱하기 할 때 앞자리 많은 수들은 0을 만들어내는 것과 관계가 없으므로. 

코드는 아래와 같이.. 짧게 @_@;

#include <stdio.h>

int main()
{
	int N = 0, zeros = 0;
	int mult = 1;

	scanf("%d", &N);

	for(int i=1; i<=N; i++) 
	{
		int div = 10;

		mult *= i;
		while(mult % div == 0) 
		{ 
			div *= 10; 
			zeros++;
		}

		mult /= (div/10);
		mult %= 100000;
	}

	printf("%d %d\n", zeros, mult%10);

	return 0;
}