글 읽기 - 시간 초과가 계속 떠서 최적화를 시켰는데 계속 시간초과뜨네요,,

qkrwnstns52 4년 전 0

어떻게 더 최적화 할 수 있울까요

#include<iostream>
using namespace std;

long long calc(int n)
{
	int i;
	long long sum = 0;
	for (i = 1; i*i < n; i++) {
		if (n%i == 0) {
			sum += i;
			sum += n / i;
		}
	}
	if (i*i == n)
		sum += i;
	return sum;
}

long long gx(int n)
{
	long long sum = 0;
	for (int i = 1;i <= n; i++)
		sum += calc(i);
	return sum;
}

int main()
{
	int n;
	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		cout << gx(num) << "\n";
	}
}

portableangel 4년 전 0

쿼리당 O(Nsqrt(N))번 실행되고 있는데, 직접 100만을 여러 번 넣어 보시고 얼마나 느린 지 보시면 됩니다.

이 문제에서는 훨씬 빠른 방법이 필요하고, 현재 코드로는 극한까지 개량과 최적화를 해도 정답을 받을 수가 없습니다.

qkrwnstns52 4년 전 0

그럼 어떻게 고치죠??? 알려주세요

portableangel 4년 전 0

고쳐서는 해결이 안 되고, 시간복잡도 자체가 다른 알고리즘을 쓰셔야 합니다.

그냥 아무 다른 작업 없이 이 문제의 제목을 구글에 복사 붙여넣기만 했더니 잘 설명된 블로그가 뜨네요. https://mygumi.tistory.com/122

park780172 4년 전 0

이 문제 세그먼트 트리로 풀었는데 다른 분 코드 보니 이럴 필요가 없었네요..... ㅠ

qkrwnstns52 4년 전 0

다른 분 코드좀 보여주세요.. 공부좀하게

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