글 읽기 - 문제를 어떻게 풀어야 할지 모르겠습니다 ㅠㅠ

wjdclgns12 8년 전 0

각 숫자를 소인수분해했을 때 2의 개수 5의 개수를 각각 구해서

둘중 작은 값을 넣는 식으로 푸려고 하니까 무조건 시간초과가 뜨네요 ㅠㅠ

제 코드에 문제가 있는지, 아니면 다른 방식으로 풀어야 하는 건지

힌트 조금만 주시면 감사하겠습니다!

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int checkTwo(int num)
{
	int result = 0;
	while (num % 2 == 0)
	{
		num /= 2;
		result++;
	}
	return result;
}
int checkFive(int num)
{
	int result = 0;
	while (num % 5 == 0)
	{
		num /= 5;
		result++;
	}
	return result;
}
int main()
{
	int n, r;
	scanf("%d %d", &n, &r);
	if (r > n - r)	
		r = n - r;
	int two = 0, five = 0;
	for (int i = 0; i < r; i++)
	{
		two += checkTwo(n - i);
		five += checkFive(n - i);
		two -= checkTwo(i + 1);
		five -= checkFive(i + 1);
	}
	printf("%d", min(two, five));
	return 0;
}

kesakiyo 8년 전 2

http://blog.janmr.com/2010/10/prime-factors-of-fac...

이 글을 보시는게 조금 힌트가 될 수 있을거에요.

yetree 8년 전 0

최대 2,000,000,000까지의 숫자가 나오니 2의갯수와 5의갯수를 센 후 둘중 최소값을 찾는게 시간이 많이 걸리지요!

한번 50 100 200의 2와 5의 갯수를 세보세요 ㅎㅎ

wjdclgns12 8년 전 1

해결했습니다 감사합니다!

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

문제

문제

출처

ICPC

문제를 어떻게 풀어야 할지 모르겠습니다 ㅠㅠ

wjdclgns12 8년 전 0

kesakiyo 8년 전 2

yetree 8년 전 0

wjdclgns12 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말