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

도서출판 인사이트에서 진행하는 알고리즘 코딩 이벤트 문제가 재밌어보여서 집에 와서 잠깐 만들어보았다. 문제는 다음과 같다:

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

[실행 예]

input n: 15
output: 3 8

[설명]

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

(전체 문제는 여기를 참조.)

별로 어려울 것은 없었지만, 초반에 약간의 시행착오가 있었다. 좀 궁리해봤더니,

“임의의 수x와 n 자리수의 값의 곱을 y라고 할 때, y의 n자리수에 영향을 미치는 x의 자리수는 n”

이라는 것을 알 수 있었다.

즉, 12345 * 99 = 1222155 이지만, 결과값의 마지막 두 자리수 55를 얻어내려면 12345의 마지막 두 자리 수, 즉 45만 사용해도 된다는 것이다. 45 * 99 = 4455 로 마지막 두자리 수 55를 얻어내는 데는 충분하다.

수학적으로 잠시 증명하자면, 위의 경우 12345 는 12300 + 45 로 따로 생각할 수 있기에 12345 * 99 = 12300 * 99 + 45 * 99 가 되는데, 12300 * 99는 이미 마지막 두 자리수에 영향을 주지 못하므로 45 * 99 만 계산하면 된다는 걸 알 수 있다.

어째건간에 위의 성질을 이용하면 100보다 작은 수를 곱할 때는 곱해지는 수는 마지막 두 자리수만 고려하면 되고, 마찬가지로 1000보다 작은 수를 곱할 때는 마지막 세 자리수만 고려하면 되고, 10000보다 작은 수를 곱할 때는 마지막 네 자리수만 고려하면 된다. 아 물론, 10보다 작은 수를 곱할 때는 마지막 한 자리수만 고려하면 된다.

프로그램은 C로 작성했다. 프로그래밍 자체는 별다른 트릭이 없다. C 언어에서는 함수 리턴값이 하나로 제한적이므로 재귀호출을 좀 더 멋지게 사용하지 못하고 전역변수를 써버린게 좀 억울하달까. 파이썬으로 했으면 좀 더 멋지게 했겠지만, 집에서 쓰는 컴에는 파이썬을 깔아놓질 않았다;

자 이제 쏘스 난무다.

#include <stdio.h>
#include <stdlib.h>

int last_facto = 1, num_zeros = 0;

void factorial(int num)
{
if(num == 1)
{
last_facto = last_facto % 10;
return;
}

last_facto = num * last_facto;

while(last_facto % 10 == 0)
{
num_zeros++;
last_facto = last_facto / 10;
}

if(num < 10)
{
last_facto = last_facto % 10;
}

else if(num < 100)
{
last_facto = last_facto % 100;
}

else if(num < 1000)
{
last_facto = last_facto % 1000;
}

else if(num < 10000)
{
last_facto = last_facto % 10000;
}

factorial(num – 1);
}

void main(void)
{
int num;
printf(“input n: “);
scanf(“%d”, &num);

factorial(num);

printf(“output: %d %d\n”, num_zeros, last_facto);
return;
}

문제에서 요구하는 결과인 2012!는 끝의 0의 갯수 501, 0 이전의 마지막 수 8이고, 10000!은 끝의 0의 갯수 2499, 0 이전의 마지막 수 8이다.

실행 결과 화면

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중

%d 블로거가 이것을 좋아합니다: