글 읽기 - C 틀렸습니다. 제가 생각한 알고리즘이 맞는건지 모르겠네요

jhhh2222 3년 전 0

분명 간과한게 있을거같은데 더이상 떠오르지 않네요 ㅠ

#include <stdio.h>

//마지막 자리만 가지고 계산
int main(void)
{
	int n;
	int fact=1;
	int count = 0;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		fact *= i; 
		if (fact % 10 == 0)  //10의 배수가 나오면 0의 개수 올려줌
		{
			count++;
			fact = 1;
		}
		else 
		{
			fact = fact % 10;
		}
	}

	printf("%d", count);

	return 0;
}

kms9937 3년 전 1

우선 제가 푼 방식으로 힌트를 드리자면 10은 2와 5를 소인수로 가집니다.

그런데 n!의 대부분의 경우 소인수 2의 개수가 5의 개수보다 훨씬 많습니다.

그러므로 5로 한번 나눠질 때마다 끝에 0이 1개씩 추가가 됩니다.(그리고 n이 작은 수 일때는 예외처리가 필요합니다.)

jhhh2222 3년 전 1

감사합니다 덕분에 해결하는데 도움 되었습니다
원래 방법보다 간편한 방법으로 해결 했지만

일단 원래 방법은 예를 들어 25*4일때 100이므로 0이 두개 더 붙는데 1개만 붙는걸로 되어버려서 틀리네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C 틀렸습니다. 제가 생각한 알고리즘이 맞는건지 모르겠네요

jhhh2222 3년 전 0

kms9937 3년 전 1

jhhh2222 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말