글 읽기 - 1912번 질문입니다!!!

pkc4913 6년 전 0

저는 재귀함수로 코드짰는데 시간초과라고 뜹니다...

어디가 문제인걸까요

그리고 제가 C언어를 독학으로 해서 코드에 잘못된 습관이 많을겁니다

혹시 고치면 좋을부분좀 지적해주세요!!!

#include <stdio.h>
#include <stdlib.h>
int SumTable[500000];
int I = 0;
int FindMax(int* arr, int ArrMax)
{
	int Max = arr[0];
	for (int i = 1; i <= ArrMax; i++)
	{
		if (arr[i] >= Max)
		{
			Max = arr[i];
		}
	}
	return Max;
}
void ContiSum(int Left, int Right, int* arr, int ArrMax)
{

	int sum = 0;
	for (int i = Left - 1; i < Right; i++)
	{
		sum = sum + arr[i];
	}
	SumTable[I] = sum;
	I++;

	if (Left == Right)
	{
		return;
	}

	ContiSum(Left, Right - 1, arr, ArrMax);
	if (Right == ArrMax)
	{
		ContiSum(Left + 1, Right, arr, ArrMax);
	}
}
int main()
{
	int n;
	scanf_s("%d", &n);
	int *ContiTable = (int*)malloc(sizeof(int) * n);
	int i = 0;
	while (i != n)
	{
		scanf_s("%d", &ContiTable[i]);
		i++;
	}

	ContiSum(1, n, ContiTable, n);


	printf("%d", FindMax(SumTable, (n*(n + 1)) / 2));
	

}

klimmek55 6년 전 0

n이 최대 10만인데 모든 경우를 보면 50억 가지 정도의 경우가 생기겠네요

거기다가 합을 구하기까지 해야하니 50억보다 훨씬 많은 연산을 해야 돼서 시간초과가 됩니다

시간제한이 2초면 연산을 2억번 정도 할 수 있는데, 모든 경우를 다 보면 안 되니까

모든 구간을 보지 않고 답을 찾을 수 있는 방법으로 푸셔야해요

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

문제

문제

출처

ICPC

1912번 질문입니다!!!

pkc4913 6년 전 0

klimmek55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말