글 읽기 - 런타임에러

kch1285 6년 전 0

안녕하세요

제 알고리즘은 일단 수를 받고 그 수들중 인접한 수들의 차이를 반복문으로 구합니다 (수가 2개남을때까지)

예를 들어 34 58 106 142가 들어왔을때,

34 58 106 142

24(58-23) 48(106-48) 36(142-106)

24(48-24) 12(48-36) 이런식으로요.

남은 2개의 수의 최대공약수의 약수를 답으로 생각했습니다.

제 코드중에서 어디 틀린부분이 있을까요.. 아니면 알고리즘 자체가 잘못됬나요 ??

#include <stdio.h>
//최대공약수
int gcd(int a,int b){
	int h,l,r=1;
	if(a>b){
		h=a;
		l=b;
	}
	else{
		h=b;
		l=a;
	}
	while(r>0){
		r=h%l;
		h=l;
		l=r;
	}
	return h;
}
//제곱근 함수
double sqrt_num(int num){
	double tmp = 1;
	while(-0.01 > (tmp *tmp-num) || (tmp*tmp-num) > 0.01)
		tmp = 0.5*(tmp+num/tmp);
	return tmp;
}

int main(){
	int n, arr[100],k,t,s,c,result[9999999];
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
    //수가 2개남을 떄까지 차를 구하는 알고리즘
	while(n>2){
		for(int i=0;i<n-1;i++){
			if(arr[i+1] > arr[i])
				arr[i] = arr[i+1] - arr[i];
			else
				arr[i] = arr[i] - arr[i+1];
		}
		n--;
    }
    //남은 두수의 최대공약수 = k
	k = gcd(arr[1],arr[0]);
    // k의 약수를 구하는 알고리즘
	t=0;
	c = (int)sqrt_num(k);
	for(int s=1;s<c+1;++s){
		if(k%s==0)
			result[t++] = s;
	}
	s=0;
	for(int j=t*2;j!=0;--j){
		if(result[j]==0){
			if(result[s] !=0 && k/result[s] != result[s])
				result[j]=k/(result[s++]);
		}
	}
    //1빼고 약수들 출력
	for(int j=0;j<=t*2;j++){
		if(result[j]!=0 && result[j]!=1)
			printf("%d ",result[j]);
	}
	printf("\n");
	return 0;
}

evenharder 6년 전 0

알고리즘은 얼추 맞습니다만, 다음 경우를 생각해봅시다.

1 4 7 10

while문을 거치고 나면 arr[0], arr[1]에는 0이 저장됩니다. gcd(0,0)을 부르면 0으로 나누기가 실행되니 멈출 수밖에 없습니다.

이는 인접한 수들의 차는 0이 될 수 없지만 이 차들의 차는 0이 될 수 있기에 발생하는 문제입니다.

때문에 while문을 돌릴 필요 없이, 인접한 수들의 차의 최대공약수를 구하면 됩니다.

evenharder 6년 전 0

추가로, main 함수에 크기 10^7짜리 배열을 집어넣는 건 환경에 따라서 런타임 에러를 일으킬 수 있습니다. 만일에 대비하여 전역 변수로 만드세요.

kch1285 6년 전 0

답변 감사합니다. 원래는 인접한 수들의 차의 최대공약수를 구하는 알고리즘을 생각했는데, n이 커서 인접한 수들의 차가 많을 경우때문에 while문 돌려서 수를 2개 남기고, 그 2개의 수의 최대공약수를 구해도 된다 생각했습니다. 저기에 arr[0]와 arr[1]의 수가 같을 경우를 if문으로 추가해서 알고리즘을 다시 짜도 될련지요.

evenharder 6년 전 0

인접한 수들의 차의 최대공약수를 구해야 하는 것이 맞습니다.

a,b,c의 최대공약수는 gcd(a,b)와 c의 최대공약수와 같기 때문에 반복문으로 확인하시면 됩니다.

처음 두 인접한 수들의 차의 최대공약수를 구하고, 그 수와 다른 차의 최대공약수를 구하고, 또 그 수와 다른 차의 최대공약수를 구하는 방식으로요.

그리고 위의 gcd 알고리즘은 a==b이면서 a!=0인 경우를 잘 처리하고 있기에 굳이 if문을 추가할 필요는 없을 듯 합니다.

kch1285 6년 전 0

감사합니다!

kch1285 6년 전 0

흐...여전히 런타임에러가뜨네요...

#include <stdio.h>

int gcd(int a,int b){

	int h,l,r=1;

	if(a>b){

		h=a;

		l=b;

	}

	else{

		h=b;

		l=a;

	}

	while(r>0){

		r=h%l;

		h=l;

		l=r;

	}

	return h;

}

int main(){

	int n, arr[100],k,t=0,result[100];

	scanf("%d",&n);

	for(int i=0;i<n;i++)

		scanf("%d",&arr[i]);

	for(int i=0;i<n-1;i++){

		if(arr[i+1] > arr[i])

			arr[i] = arr[i+1] - arr[i];

		else

			arr[i] = arr[i] - arr[i+1];

	}

	for(int i=1;i<=n-2;i++){

		k = gcd(arr[0],arr[i]);

		arr[0] = k;

	}

	for(int i=1;i<=arr[0];i++){

		if(arr[0] % i ==0){

			result[t]=i;

			t++;

		}

	}

	for(int i=0;i<t;i++){

		if(result[i]!=1){

			printf("%d ",result[i]);

		}

	}

	printf("\n");

	return 0;

}

evenharder 6년 전 0

약수가 100개가 넘어갈 수 있기 때문입니다.

3
24300000
48600000
72900000

의 경우 차이가 24300000인데 이 수는 약수의 개수가 216개이기 때문에 result 배열의 크기를 초과하게 됩니다.

그리고 1에서부터 arr[0]까지 약수를 확인하는 것은 시간 제한이 걸릴 수도 있습니다. 예를 들면

3
111111111
555555555
999999999

같은 경우에서요. x가 n의 약수이면 n/x도 n의 약수임을 이용해보세요. 보다 빠르게 문제를 풀 수 있습니다.

std::vector를 한 번 구글링해보시는 것도 좋을 듯 합니다.

kch1285 6년 전 1

덕분에 풀었습니다 감사합니다

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

문제

문제

출처

ICPC

런타임에러

kch1285 6년 전 0

evenharder 6년 전 0

evenharder 6년 전 0

kch1285 6년 전 0

evenharder 6년 전 0

kch1285 6년 전 0

kch1285 6년 전 0

evenharder 6년 전 0

kch1285 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말