글 읽기 - (c언어)시간초과가 나오는 조건을 모르겠습니다

hdh050901 2년 전 0

계속 시간초과가 나오는데 시간초과가 나오는 조건을 모르겠네요;;

반례좀 찾아주시면 감사하겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int m, M;//minimum,maximum
	scanf("%d %d", &m, &M);
	for (int count1 = m; count1 <= M; count1++) {
		if (count1 == 1) {
			dd:
			continue;
		}
		for (int count2 = 2; count2 < count1; count2++) {
			if (count1 % count2 == 0)
				goto dd;
		}
		printf("%d\n", count1);
	}
	return 0;
}

bamgoesn 2년 전 3

goto를 쓰신 것도 좀 그렇지만... 시간 초과가 goto때문에 발생한 것은 아닌 것으로 보입니다.

작성하신 코드는 count1을 m부터 M까지 바꿔가는 동안, 2부터 count1까지의 모든 수로 count1을 나눠보는 코드로 보입니다.

최악의 경우 count1을 count1까지 모든 수에 대해 나눠보게 되고, 실제로 평균적으로도 나누는 횟수가 count1에도 비례하기 때문에, 이 코드의 시간복잡도는 O((M-m)^2)입니다. 현재 M-m은 최대 100만이기 때문에 이 시간복잡도로는 제한시간을 통과하기 어렵습니다. (실제로 m=1, M=1000000이면 루프 횟수는 370억회 정도 됩니다.)

따라서 더 효율적인 다른 방법을 사용하셔야 합니다.

hdh050901 2년 전 0

루프에서 못나오는것으로만 생각하고 있었는데 복잡도는 생각못해봤네요

더효율적인 방법을 생각해봐야겠습니다

감사합니다^^

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

문제

문제

출처

ICPC

(c언어)시간초과가 나오는 조건을 모르겠습니다

hdh050901 2년 전 0

lbj0126 2년 전 0

bamgoesn 2년 전 3

hdh050901 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말