글 읽기 - 1912번 문제 시간초과가 뜨는데.. 어떻게 수정해야 할까요??ㅠㅠ

dmsgh7678 8년 전 0

시간초과가 뜨네요... 어떻게 해야 할지..

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

int main(void)
{
	int a;
	int *num;
	int i,j,k;
	int result, sum=0;
	scanf("%d",&a);
	num=(int*)malloc(sizeof(int)*a);

	for(i=0;i<a;i++)
		scanf("%d",&num[i]);

	result=num[0];
	for(i=0;i<a;i++)
	{
		for(j=0;j<a-i;j++)
		{
			for(k=0;k<i+1;k++)
			{
				sum+=num[j+k];
			}
			if(sum>result)
				result=sum;
			sum = 0;
		}
	}
	printf("%d\n",result);

}

onjo0127 8년 전 1

3중 for문이면 시간 내에 해결할 수 없습니다...

다이나믹 프로그래밍이라는 알고리즘을 공부하셔서 for문 하나만으로 해결해야 합니다

인터넷에 좋은 자료가 많으니 인터넷에서 찾아보셔도 좋고 알고리즘 관련 책을 하나 사시는 것도 좋습니다.

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

문제

문제

출처

ICPC

1912번 문제 시간초과가 뜨는데.. 어떻게 수정해야 할까요??ㅠㅠ

dmsgh7678 8년 전 0

onjo0127 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말