선생님, 28번 문제를

Question

'일의 자리부터 연속적으로' 가 아니라 N!값을 구하였을 때, 일의자리부터 10의 자리는 모두 00이지만 중간에 000이나 0000이 나오게 되는 경우로 문제를 변형하였을 경우에는 어떻게 푸는게 제일 효율적일지 궁금합니다.  1) N!값을 구한 뒤 그 값을 char로 형변환 한 다음 하나씩 탐색해나가면서 연속된 0의 개수를 구하는 방법  현재로서는 이 방법 밖에 떠오르지 않는데.... 혹시 별 다른 방법이 있을까요? 궁금합니다 .

김태원 · Answer

그렇게 문제를 바꾸면 엄청 어려운 문제가 되고 코드구현도 굉장히 복잡해집니다. 일단 N제한이 1000이기 때문에 N!값이 너무 커서 정수형 변수에 들어가지 않습니다. 그래서 N!값을 계산하는 것 자체가 힘듭니다. 만약 정수형 변수에 계산이 됬다면 계산된 값을 10으로 나눈 몫으로 계속 바꿔가면서 그 몫을 10으로 나눈 나머지가 0인지 확인하는 것이 좋을 것 같습니다. #include<stdio.h> int main() { long long N=8070008700210; while(N>0){ int t=N%10; printf("%d
", t); N=N/10; } return 0; } N!을 계산할 때는 일반적인 연산 코드를 쓰는 것이 아니라 알고리즘에 큰수 곱셈이라는 알고리즘이 있습니다. 이 방법을 써서 N!값을 구해야 하는데 많이 복잡합니다. 단순 두 개의 큰수를 곱하는 것도 아니구 N!을 큰 수 곱셈으로 구현하는 것은 엄청 복잡할 것 같습니다.  나중에 실력자가 되시면 도전해보시기 바랍니다.