글 읽기 - C언어 시간초과

wodus0129 3년 전 0

다음과 같이 작성했는데 시간초과가 발생합니다......

어떻게 해결 가능한가요.....?

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

int main(void) {
	int* arr, len;

	scanf("%d", &len);
	arr = (int*)malloc(len * sizeof(int));

	for (int i = 0; i < len; i++)
		scanf("%d", &arr[i]);

	int maximum = arr[0];
	if(arr != NULL)
    {
        for (int i = 0; i < len - 1; i++)
	    {
		    int hap = arr[i];
		    for (int j = i + 1; j < len; j++)
		    {
			    hap += arr[j];
			    if (hap > maximum)
				    maximum = hap;
		    }
	    }
    }
    free(arr);
	printf("%d\n", maximum);

	return 0;
}

adxx 3년 전 0

N이 10만이라 N^2풀이는 시간초과받는게 당연하겠네요

O(N)풀이도 있지 않을까요?

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

문제

문제

출처

ICPC

C언어 시간초과

wodus0129 3년 전 0

adxx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말