글 읽기 - 1280_나무심기 시간초과질문!

rmstjr1213 5년 전 0

제가 처음으로 시간초과 오류를 받았는데

일단 알고리즘이 틀려서 그런지 아니면 알고리즘은 맞지만 최적화가 안되서 그런지 문제점 부터 잘 모르겠습니다.

어떻게 해결해야 되는지 감이 안옵니다.

(재귀함수가 속도를 느리게 할 수 있다고해서 for문으로도 바꿔보았고

지역변수를 줄이면 좋다고 해서 전역변수로도 바꾸어 보았는데 둘다 안되었습니다)

#include<stdio.h>

void Caculate(int i, int coordinate[]);

static int Store=1;

int main() {
	int namuNum;
	int* coordinate;
	int result;
	
	//나무 개수를 받음
	scanf("%d", &namuNum);
	//배열을 만듬
	coordinate = (int *)malloc(namuNum * sizeof(int));
	for (int i = 0; i < namuNum; i++) {
		scanf("%d", &coordinate[i]);
	}
	Caculate(namuNum - 1 , coordinate);
	
	result = Store % 1000000007;
	printf("%d", result);	
}


void Caculate(int i, int coordinate[])
{
	int result;
	int temp = 0;
	for (int j = i; j > 0; j--) {
		result = coordinate[i] - coordinate[j-1];
		if (result > 0)
			temp += result;
		else
			temp += (result*-1);
	}
	
	Store *= temp;
	i -= 1;
	if (i > 0) {
		Caculate(i, coordinate);
	}
}

djm03178 5년 전 0

시간복잡도를 계산해 보세요. n+(n-1)+(n-2)+...1 이니까, O(n^2)입니다. 20만의 제곱은 약 400억인데, 프로그램이 1초에 돌릴 수 실행할 수 있는 양은 많아야 20억입니다.

rmstjr1213 5년 전 0

공부하면서 시간복잡도는 스킵했었는데 이럴때 확실히 알수 있네요!!

감사합니다!

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

문제

문제

출처

ICPC

1280_나무심기 시간초과질문!

rmstjr1213 5년 전 0

djm03178 5년 전 0

rmstjr1213 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말