-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
선생님, 28번 문제를
20.03.04 21:25 작성 조회수 138
0
'일의 자리부터 연속적으로' 가 아니라
N!값을 구하였을 때, 일의자리부터 10의 자리는 모두 00이지만 중간에 000이나 0000이 나오게 되는 경우로 문제를 변형하였을 경우에는 어떻게 푸는게 제일 효율적일지 궁금합니다.
1) N!값을 구한 뒤 그 값을 char로 형변환 한 다음 하나씩 탐색해나가면서 연속된 0의 개수를 구하는 방법
현재로서는 이 방법 밖에 떠오르지 않는데.... 혹시 별 다른 방법이 있을까요? 궁금합니다 .
답변을 작성해보세요.
1
김태원
지식공유자2020.03.04
그렇게 문제를 바꾸면 엄청 어려운 문제가 되고 코드구현도 굉장히 복잡해집니다.
일단 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\n", t);
N=N/10;
}
return 0;
}
N!을 계산할 때는 일반적인 연산 코드를 쓰는 것이 아니라 알고리즘에 큰수 곱셈이라는 알고리즘이 있습니다. 이 방법을 써서 N!값을 구해야 하는데 많이 복잡합니다. 단순 두 개의 큰수를 곱하는 것도 아니구 N!을 큰 수 곱셈으로 구현하는 것은 엄청 복잡할 것 같습니다. 나중에 실력자가 되시면 도전해보시기 바랍니다.
답변 1