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

문제

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

자연수 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 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

 

풀이

factorial 이므로 모든 곱에서 0이 나오는 경우는 2,5가 포함되어 있을 경우이다. 다르게 말해, n! = (2*5)*k 로 표현가능하다. 즉, 2와 5가 몇 개나 포함되어 있는지를 찾는 것이 이 문제의 요지이다. 10들은 다 제외했고, 이제 그 앞의 수는 나머지 k의 10의 modulo로 나올 것이다.

* 심화 문제는 간단하다. 0 앞에 나오는 여러 숫자는 결국 modulo의 크기에 달려있다. 두자리면 100으로 modulo를 구하면 되고, 세자리면 1000으로 구하면 된다.


input n: 2012
output : 501 8

input n: 10000
output : 2499 8

(심화 - 2자리)
input n: 2012
output : 501 28

input n: 10000
output : 2499 08

* n = 10000 인 경우 ...9008000...로 나간다 (계산이 틀리지 않았다면ㅋㅋ)


소스코드

코드는 2와 5를 세고, 2*5 의 개수를 카운팅 한 뒤 남는 2나 5의 개수만큼 나머지에서 곱해서 modulo를 구한다. 나머지의 경우 루프마다 modulo를 하고 2와 5의 경우 5는 무조건 modulo(10)이 5이고 2의 경우에는 (2,4,8,6)의 반복임을 이용해서 오버플로우의 가능성을 없앴다. 물론 심화 문제처럼 하려면 2나 5중 남는 개수를 루프로 modulo 하면 되겠다.

void    findZero(const int n)
{
int res = 1;
int twos = 0;
int fives = 0;
int zeros = 0;
int PowOfTwo[4] = {2,4,8,6};

// find 2s and 5s, and get the modulo of residues
for(int i = n; i > 1; --i)
{
int num = i;

while(num%2 == 0)
{
num /= 2;
++twos;
}

while(num%5 == 0)
{
num /= 5;
++fives;
}
res = (res*num)%10;
}

zeros = (twos > fives) ? fives : twos;
if(fives - twos > 0) res = (res*5)%10;
else if(twos - fives > 0) res = (res*PowOfTwo[(twos-fives-1)%4])%10;

printf("%d %d", zeros, res);
}

핑백

  • 문제 풀이 이벤트 당첨자 발표! | 도서출판 인사이트 2012-10-09 07:02:24 #

    ... m4 님. (총 세 문제에 열정적으로 도전하신 덕인가 봅니다. ^^ ^^) 그냥 이대로 널 보내야만 하는가... ㅡㅜ 다음으로 라스베리 파이 다섯 대를 받으실 분… 3번 문제에 응모하신 ins7itia 님 3번 문제에 응모하신 daejin 님 4번 문제에 응모하신 ummae 님 3번 문제에 응모하신 lozephon 님 1번 문제에 응모하신 Abra ... more

덧글

댓글 입력 영역