글 읽기 - 시간초과 질문입니다!

oh20020409 3년 전 0

언제나 답변 달아주시는 분들께 감사드립니다.

답이 매우 잘 나오는 것 같은데요!

시간 초과가 발목을 잡습니다.

제 방법은 입력된 수로 모두 나누어 떨어지면서, 약수의 개수와 입력한 개수가 같아햐 한다로 풀었습니다.

예를 들어

3 9를 입력하면

18은 2*3^2 이므로1* 2*3 - 2(1,18은 제외) = 4개가 나오며

27은 3^3 이므로 1*4 - 2(1,27은 제외) 로 2개가 나오기 때문에 27이 정답이 됩니다.

어떻게 더 잘 만들 수 있을지 도와주시겠어요?

#include<iostream>
using std::cin;
using std::cout;
using std::endl;
int main()
{
	int N;
	cin >> N;
	int i;
	int *ptr = new int[N];
	int num = 1;
	int max = 0;
	for (i = 0; i < N; i++)
	{
		cin >> ptr[i];
		if (max < ptr[i]) max = ptr[i];
	}
	while (1)
	{
		int check = 1;
		for (i = 0; i < N; i++)
		{
			if (num%ptr[i] != 0)
			{
				check = 0;
				break;
			}
		}
		// 약수의 개수 구하는 방법//

		int a = num; 
		i = 2;
		int sum=1;
		int checking = 1;
		while (1)
		{
			if (a%i == 0)
			{
				a /= i;
				checking++;
			}
			else
			{
				i++;
				sum *= checking;
				checking = 1;
			}
			if (a == 1)
			{
				sum*=checking;
				break;
			}
		}
		sum = sum - 2;		
		//
		if (check == 1 && num != max && sum == N ) // 다 나누어지고 약수의 개수가 같으면 출력
		{
			cout << num;
			break;
		}
		num++;
	}
	delete[]ptr;
}

oh20020409 3년 전 0

실제로 여러번 다양한 수들을 입력해보니 너무 시간이 길어지네요.

다른 방법을 이용했습니다!

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

문제

문제

출처

ICPC

시간초과 질문입니다!

oh20020409 3년 전 0

oh20020409 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말