글 읽기 - c언어 시간초과 및 틀린이유가 무엇때문일까요?ㅠ

projung0722 2년 전 0

1,2,3번 코드가 왜 틀렸는지 잘 모르겠습니다. 도와주십쇼!ㅠ

1. 틀린코드 //두수의 차를 절대값을 이용해서 정렬하지않고 바로 배열의 값 사용해서 최대공약수 구함.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define max(a,b) (((a)>(b)?(a):(b)))

int main()
{
	int N;
	scanf("%d", &N);
	int* arr;
	arr = (int*)malloc(sizeof(int) * N);
	int* diff;
	diff = (int*)malloc(sizeof(int) * (N-1));
	scanf("%d", &arr[0]);
	for (int i = 1; i < N; i++) {
		scanf("%d", arr + i);
		diff[i - 1] = abs(arr[i] - arr[i - 1]);
	}
	int tmp = arr[1] - arr[0];
	for (int i = 2; i < N; i++)
		tmp = gcd(tmp, abs(arr[i] - arr[i - 1]));
	int i = 2;
	while (1) {
		if (i > tmp)
			break;
		else {
			if (tmp % i == 0)
				printf("%d ", i);
		}
		i++;
	}
	return 0;
}

int gcd(int x, int y)
{
	int tmp;
	if (x < y) {
		tmp = x;
		x = y;
		y = tmp;
	}
	while (y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

2.시간초과 코드 //arr를 정렬하여 두수의 차를 구해서 두수의 차들의 최대공약수 구함.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define max(a,b) (((a)>(b)?(a):(b)))

int compare(const void* n1, const void* n2)
{
	int x, y;
	x = *(int*)n1;
	y = *(int*)n2;
	if (x > y)
		return 1;
	else if (x < y)
		return -1;
	else
		return 0;
}

int main()
{
	int N;
	scanf("%d", &N);
	int* arr;
	arr = (int*)malloc(sizeof(int) * N);
	int* diff;
	diff = (int*)malloc(sizeof(int) * (N - 1));
	scanf("%d", &arr[0]);
	for (int i = 1; i < N; i++) {
		scanf("%d", arr + i);
		diff[i - 1] = abs(arr[i] - arr[i - 1]);
	}
	qsort(arr, N, sizeof(int), compare);
	int tmp = arr[1] - arr[0];
	for (int i = 2; i < N; i++)
		tmp = gcd(tmp, arr[i] - arr[i - 1]);
	int i = 2;
	while (1) {
		if (i > tmp)
			break;
		else {
			if (tmp % i == 0)
				printf("%d ", i);
		}
		i++;
	}
	return 0;
}

int gcd(int x, int y)
{
	int tmp;
	if (x < y) {
		tmp = x;
		x = y;
		y = tmp;
	}
	while (y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

3.또 다시 틀린 코드 //약수를 구할때 반복문을 절반만 돌리도록 수정.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define max(a,b) (((a)>(b)?(a):(b)))
int sol[500];
int compare(const void* n1, const void* n2)
{
	int x, y;
	x = *(int*)n1;
	y = *(int*)n2;
	if (x > y)
		return 1;
	else if (x < y)
		return -1;
	else
		return 0;
}

int main()
{
	int N;
	scanf("%d", &N);
	int* arr;
	arr = (int*)malloc(sizeof(int) * N);
	int* diff;
	diff = (int*)malloc(sizeof(int) * (N - 1));
	scanf("%d", &arr[0]);
	for (int i = 1; i < N; i++) {
		scanf("%d", arr + i);
		diff[i - 1] = abs(arr[i] - arr[i - 1]);
	}
	qsort(arr, N, sizeof(int), compare);
	int tmp = arr[1] - arr[0];
	for (int i = 2; i < N; i++)
		tmp = gcd(tmp, arr[i] - arr[i - 1]);
	int count = 0;
	for (int i = 1; i * i <= tmp; i++) {
		if (tmp % i == 0) {
			sol[count++] = i;
			if (i != tmp / i)
				sol[count++] = tmp / i;
		}
	}
	for (int i = 0; i < count; i++) {
		if (sol[i] != 1)
			printf("%d ", sol[i]);
	}
	printf("\n");
	qsort(sol, count, sizeof(int), compare);
	for (int i = 0; i < count; i++) {
		if (sol[i] != 1)
			printf("%d ", sol[i]);
	}
	return 0;
}

int gcd(int x, int y)
{
	int tmp;
	if (x < y) {
		tmp = x;
		x = y;
		y = tmp;
	}
	while (y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

ppsrac 2년 전 1

1번 코드는 tmp 변수 초기화 시 (20번째 줄) 절대값을 해주지 않아 arr[1]<arr[0]인 경우 오류가 납니다.(반례 : 3/5 3 7 정답:2 출력: 없음)

2번 코드는 수를 출력하는 과정에서 gcd의 크기 n이 크다면 최대 n번의 연산을 하기 때문에 시간 초과 오류가 난 것 같습니다. 3번처럼 sqrt(n)이하로 나누는 것으로 고친다면 굉장히 빨라질 것입니다.

3번 코드는 일단 출력이 잘못 된것 같습니다. 두번 출력됩니다.

입력: 3/16 32 48

출력:

16 2 8 4
2 4 8 16

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

문제

문제

출처

ICPC

c언어 시간초과 및 틀린이유가 무엇때문일까요?ㅠ

projung0722 2년 전 0

ppsrac 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말