1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
내가 푼 풀이는 틀렸다ㅠ (정답은 맨 아래에 있다)
N의 범위가 0부터 500까지이므로 수가 매우 커져버린다
따라서 1부터 N까지 곱하는데 0이 생길 때마다 0의 개수를 count 해주는 방식으로 코드를 짜보았다
int num = 1;
for (i = 1; i <= N; i++) {
num *= i;
while (num >= 10) {
if (num % 10 == 0) { // 일의 자리가 0이 되면
cnt++; // 0이 하나 생긴 것이므로
num /= 10; // 일의 자리의 0을 없앰
continue;
}
num %= 10;
}
}
음... i = 100이 되어 num에 100이 곱해지면서 0이 한 번에 두 개 이상 생기는 경우도 포함시켜주기 위해
while 문을 이용해서 num이 다시 한 자릿수가 될 때까지 num을 10으로 나눠주는 작업까지 해주었는데
그래서 완벽하다고 생각했다
N = 500도 입력해 봤는데 실제 답인 124가 똑같이 나오길래
더더욱 내 방법에 확신했다
근데 결과는...
한 40%까진가 채점하다가 '틀렸습니다'....?
N = 500까지 답이 맞게 나왔으면 그보다 작은 수에서도 당연히 정답일 거라 생각하는데
왜 틀렸다고 나오는지 아직까지 이해가 안 된다...ㅠㅠ
다른 분들의 질문을 대충 봤을 때
xxxxx125에서 4가 곱해지는 경우 1000이 되어 0이 3개 생기는데
내 풀이로 계산한다면, 일의 자릿수만 남겨 놓고 그 다음 수에 곱해지므로
실제 xxxxx125에서 4가 곱해지는 경우는
5에서 4가 곱해지는 경우가 되어
00이 아니라 20이 되는 문제가 발생하긴 한다
근데 문제에서의 최대 N인 500을 입력했을 때 답이 똑같이 나왔다면
N이 500까지에서는 저런 경우가 안 나왔을 것 같은데...
흠...
(틀린 코드 - 전체)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main() {
int N, i;
int num = 1, cnt = 0; // num: 1부터 시작하여 N!까지 계산, cnt: 0의 개수
scanf("%d", &N);
for (i = 1; i <= N; i++) {
num *= i;
while (num >= 10) {
if (num % 10 == 0) { // 일의 자리가 0이 되면
cnt++; // 0이 하나 생긴 것이므로
num /= 10; // 일의 자리의 0을 없앰
continue;
}
num %= 10;
}
}
printf("%d", cnt);
}그래서 다른 분들의 풀이를 이용하여 다시 풀어보았다
곱해서 0이 되는 경우는 2*5가 되는 경우 밖에 없다
1부터 N까지 누적하여 곱하면 2와 5가 곱해지는 경우가 매우 많아지게 된다
1부터 N까지의 수에서 2의 배수와 5의 배수의 개수를 세어주면 0의 개수를 알 수 있다
여기서 주의할 점이 있다!
5의 배수뿐만 아니라 25, 125의 배수의 개수도 세어줘야 한다
4에서 25를 곱하면 100이 되어 0이 두 개 생기는 경우도 있기 때문이다
그리고 사실 2의 배수는 세지 않아도 된다
1부터 N까지 수 중 5의 배수보다 2의 배수가 월등히 많기 때문이다
그리고 N = 5일 때 0이 처음 생기게 되는데
이는 2의 배수는 세지 않아도 된다는 걸 확실히 알려준다
따라서 코드는 아래와 같다
(정답)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main() {
int N, cnt = 0; //cnt: 0의 개수
scanf("%d", &N);
cnt += N / 5;
cnt += N / 25;
cnt += N / 125;
printf("%d", cnt);
}
난이도: solved.ac 실버 5