글 읽기 - 시간초과가 나오네요 sqrt로는 안되는건가요?

wggwvs 1년 전 0

사실 복잡도가 O(n*sqrt(n))이라 풀릴줄 알았는데 안되네요. 질문들을 검색해 보니까 sqrt로 된다는 분들도 계시고... 왜 안되는 걸까요?

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int M = 0;
	int N = 0;
	cin >> M;
	cin >> N;
	int count = 0;
	if (M == N) {
		if (M == 1 || M==4) { count++; }
		if (M == 2 || M == 3 || M == 5 || M == 7 ) { cout << M <<"\n";  }
		else {
			for (int i = 2; i < sqrt(M)+1; i++) {
				if (M % i == 0) { count++; }
			}
			if (count == 0) { cout << M<<"\n"; }
		}
	}

	else {
		for (int i = M; i < N+1; i++) {
			if (i == 1 || i==4 ) { count++; }
			if (i == 2 || i == 3 || i == 5 || i == 7) { cout << i<<"\n"; count++; }
			for (int x = 2; x < sqrt(i)+1; x++) {
				if (i % x == 0) { count++; }
			}
			if (count == 0) { cout << i<<"\n"; }
			count = 0;


		}
	}
}

djm03178 1년 전 0

sqrt는 기본적으로 매우 매우 무거운 연산입니다. 이 연산을 O(N)번만 해도 무거운데, 이를 for문의 조건문에 넣으면 루프를 도는 횟수만큼 sqrt를 계산해야 하기 때문에 시간 내에 돌 수 없습니다.

sqrt의 값을 미리 계산해서 따로 변수에 빼두고 조건문에는 변수를 넣으면 통과됩니다.

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

문제

문제

출처

ICPC

시간초과가 나오네요 sqrt로는 안되는건가요?

wggwvs 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말