글 읽기 - 시간 초과 뜨는데 왜 뜨는 건지 잘 모르겠어요

tjrdnd0511 6년 전 0

시간 초과 뜨는데 왜 뜨는 건지 잘 모르겠어요

#include <stdio.h>
#include <stdlib.h>

typedef struct tagB
{
	long long Num;
	long long Index;
}B;

int cmp(const void * a, const void *b)
{
	return ((B*)a)->Num < ((B*)b)->Num;
}

long long ABS(long long val)
{
	return (val > 0) ? val : -1 * val;
}

int A[3333];
struct tagB Res[11111];

int main(void)
{
	int N;
	int len;
	int zero = 0;
	B min = {0,0};

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", A + i);
	}

	for (int k = 1; k <= N / 2; k++)
	{
		len = 0;
		for (int i = 0; i <= N-k; i++)
		{
			for (int j = i; j < i + k; j++)
			{
				if (j == i)
				{
					Res[i].Num = A[j];
					len++;
				}
				else
				{
					Res[i].Num += A[j];
				}
				Res[i].Index = j;
			}
		}
		qsort(Res, len, sizeof(B), cmp);

		for (int i = 1; i <= N - k; i++)
		{
			if (k==1 && i == 1)
			{
				min.Num = ABS(Res[1].Num - Res[0].Num);
				min.Index = k;
				continue;
			}

			if (ABS(Res[i].Index - Res[i - 1].Index) >= k)
			{
				if (ABS(Res[i].Num - Res[i - 1].Num) <= min.Num)
				{
					min.Num = ABS(Res[i].Num - Res[i - 1].Num);
					if (min.Index < k)
					{
						min.Index = k;
					}
					if (min.Num == 0)
					{
						zero = 1;
						break;
					}
				}
			}
		}
		if (zero)
			break;
	}

	printf("%lld\n%lld\n", min.Index, min.Num);

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과 뜨는데 왜 뜨는 건지 잘 모르겠어요

tjrdnd0511 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말