글 읽기 - 안녕하세요. 런타임 에러입니다. 한번만 봐주시면 감사합니다

wjdwldud4190 6년 전 1

안녕하세요. 귀한시간 내서 봐주셔서 너무 감사합니다.

이 문제를 풀때 제가 생각한 알고리즘은

만약 예제가

3

2 3 5

2

4 5

라고 한다면 각각 인자마다 체크배열을 만들어 체크를 한 후 개수를 저장하는 것입니다. 저 위의 예제를 이용한다면

check1, check2배열, a,b배열을 이용하겠습니다.

먼저, 각각 인자를 소인수 분해합니다. 위의 첫번째입력 인자들은 이미 소수이므로 소인수분해를 거치지 않아도 되겠네요.

두번째 입력 인자들은 4 = 2*2로 소인수 분해되어 2 2 5로 이용할 것입니다.

첫 번째 입력이 2 3 5이므로 check1[2] = 1, check1[3] = 1, check1[5] = 1를 해주고 a[2] +=1, a[3] +=1, a[5] +=1

두 번째 입력이 4 5(=2 2 5)이므로 check2[2] = 2, check2[5] = 1를 해주고 b[2] +=2, b[5] +=1일 것입니다.

두 수의 최대 공약수란 공통된 인자들의 곱이므로

(check1[i]==1 & check2[i]==1)인 것들 중에서 a[i] b[i]의 공통된 숫자 만큼 곱해주는 것으로 구했습니다.

a[2] = 1, b[2] =2이므로 2가 1개 공통

a[5] = 1, b[5] = 1이므로 5가 1개 공통 => 2*5 =10

수가 많이 크기 때문에 소인수 분해하여 인자들을 따로 계산하는게 빠르다는 생각하에 했습니다.

하지만 계속해서 런타임 에러가 나서 배열 인덱스를 최대한으로 키워보고 잘못된 접근을 한것은 아닌지 디버깅 해보았지만 제 실력으론 부족하네요..

혹시 비슷한 고민을 하셧거나 아신다면 제가 놓친 부분이나 잘못된 부분을 가르쳐주시면 감사하겠습니다..ㅜㅜ

시간내주셔서 감사합니다.

//2824_최대공약수
#include <cstdio>
int a[100000001];
int b[100000001];
int input[1001];
int check1[100000001];
int check2[100000001];

void Zacada(int n, int c)//소인수분해
{
	int N = n;

	for(long long i = 2; i*i<=n ;i++)
	{
		while(n%i==0)
		{
			if(c == 1)//첫번째 입력 수
			{
				check1[i] =1;
				a[i] +=1;
			}

			else //두번째 입력 수
			{
				check2[i] = 1;
				b[i] +=1;
			}

			n = n/i;
		}
	}

	if(n>1)
	{
		if(c==1)
		{
			check1[n] =1;
			a[n] +=1;
		}
		else
		{
			check2[n] =1;
			b[n] +=1;
		}
	
	}
}

int main()
{
	int N,M,tempN,tempM;
	
	scanf("%d",&N);
	tempN = N;

	int index =0;
	////입력 시작
	while(tempN--)
	{	
		scanf("%d",&input[index++]);
	}

	//첫번째 입력된 인수들의 소인수를 저장
	for(int i = 0 ; i <N; i++)
	{
		Zacada(input[i],1);
	}

	scanf("%d",&M);
	tempM = M;

	index = 0;
	while(tempM--)
	{
		scanf("%d",&input[index++]);
	}
	
	//두번째 입력된 인수들의 소인수를 저장
	for(int i = 0 ; i <M; i++)
	{
		Zacada(input[i],2);
	}


	long long result = 1;

	//배열에 저장된 값들을 비교하면서 공통된 숫자를 곱해준다. 
	for(int i = 2; i <100000000; i++)
	{
		if(check1[i]==1 && check2[i]==1)
		{
			if(a[i]>=b[i])
			{
				for(int j = 0; j<b[i]; j++)
				{
					result*=i;
				}
			}

			else if(a[i]<b[i])
			{
				if(a[i]<b[i])
				{
					for(int j = 0; j<a[i]; j++)
					{
						result*=i;
					}
				}
			}
			
			//이부분은 일단 9자리 넘어가면 끝내려고. 수정할 예정
			if(result/100000000 > 0)
			{
				printf("%lld",result);
				return 0;
			}
			
		}
	}

	printf("%lld\n",result);

	return 0;
}

bupjae 6년 전 1

입력될 수 있는 수의 최대 크기는 10억인데, 배열 크기를 1억 만 설정하셨네요.

1억보다 큰 소수가 입력으로 들어오면 배열 범위를 넘어서서 오류가 발생합니다.

그렇다고 배열 크기를 10억으로 잡으면, 메모리 초과 오류를 보게 되겠죠

소인수 분해 결과를 저장할 수 있는 다른 자료구조를 생각하셔야 합니다.

wjdwldud4190 6년 전 1

댓글 정말 감사합니다...말씀해주신 방향으로 다시 생각해 보겟습니다.

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