글 읽기 - 시간복잡도에 관하여....

strake32 8년 전 0

안녕하세요. 코딩으로 프로그래밍 연습을 하고 있는 학생입니다.ㅎ

여기서 여러 문제를 풀다가 처음으로 시간초과라는 문제에 직면하게 되었는데,

이리저리 머리를 굴려보아도 시간복잡도를 줄일 방법이 떠오르지 않아서 질문드립니다.

여러분들은 어떻게 시간복잡도를 줄이시는지 궁금합니다.

해법이 아니더라도 어떠한 힌트를 주시면 감사하겠습니다.

요즘 날 더운데 몸 조심하세요 ㅋ

#include <stdio.h>
#include <stdlib.h>
typedef struct data{
	int start;
	int end;
	int result;
}data;

int main(void)
{
	data *a;
	int N, M;
	int *arr;
	int i = 0;
	int min=0,k=0,j=0;
	scanf("%d %d", &N,&M);
	

	arr = (int*)malloc(sizeof(int)*N);
	a = (data*)malloc(sizeof(data)*M);

	for (i = 0; i < N+M; i++)
	{
		if (i < N)
			scanf("%d", &arr[i]);
		else 
		{
			scanf("%d %d", &a[k].start, &a[k].end);
			
			a[k].result = arr[(a[k].start) - 1];
			for (j = (a[k].start)-1; j < a[k].end; j++)
			{
				if (a[k].result > arr[j])
					a[k].result = arr[j];
			}
			k++;
		}
		
	}

	for (i = 0; i < M; i++)
		printf("%d\n", a[i].result);

	return 0;
}