글 읽기 - 시간 초과 원인을 모르겠습니다.

adfsfsf 5년 전 0

시간을 줄이기 위해 check 함수에 b를 도입했고, num을 동적할당 시키는 대신에 i의 최댓값보다 적당히 큰 크기의 배열로 선언하였습니다.

n개 세트를 추가한 경우에 대해 check 함수를 실행하면 n개 미만의 세트를 추가한 경우는 이미 점검하였으므로 생략시켰습니다.

답은 맞게 나오는 것 같습니다.

#include <stdio.h>
int num[1005];
int maxnum;
int check(int a, int b, int count);
int main(void)
{
	int i, max = 0, j;
	scanf("%d", &maxnum);
	for (i = 0; i < maxnum; i++)
		scanf("%d", &num[i]);
	for (i = 0; i < maxnum; i++)
	{
		j = check(i, i + 1, maxnum - (i + 1)) + num[i];
		if (max < j)
			max = j;
	}
	printf("%d\n", max);
	return 0;
}
int check(int a, int b, int count)//a는 check에서 조사 할 num의 인덱스 + 1, count는 남은 붕어빵 수, b개 이하의 경우는 조사하지 않음
{
	int max = 0, j, i;
	if (count <= b - 1)//b개 미만의 세트에 대해서는 이미 check했으므로 0 반환
		return 0;
	else
	{
		for (i = b - 1; i < count; i++)
		{
			j = check(i, i + 1, count - (i + 1)) + num[i];
			if (max < j)
				max = j;
		}
		return max;
	}
}

djm03178 5년 전 1

이 정도만 넣어도 꽤 오랜 시간이 걸리는 걸 볼 수 있습니다.

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

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

문제

문제

출처

ICPC

시간 초과 원인을 모르겠습니다.

adfsfsf 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말