글 읽기 - 1912 c언어 질문있습니다. 시간초과...

lsmmay322 3년 전 0

코드를 짜봤는데 답은 잘 나옵니다..

근데 시간초과에서 계속 걸리네요

반복문을 한번만 써야하나요. 아니면 배열을 하나 써야하나요

시간초과를 어떻게 해결해야할지 모르곘어요ㅠㅠ

#include <iostream>
using namespace std;

int main()
{
	int n, max, res;
	int arr[100002] = { 0, };
	int sum;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	res = arr[1];
	for (int i = 2; i <= n; i++)
	{
		sum = arr[i];
		for (int j = i - 1; j >= 1; j--)
		{
			sum += arr[j];
			if (res < sum)
				res = sum;
		}
	}
	printf("%d", res);
}

sr5757 3년 전 0

이 코드는 이중포문때문에 시간복잡도가 O(n^2)가 되는데, 이 문제에서 최대 n값은 10^5이기 때문에 시간초과가 나옵니다.

DP를 사용해서 푸시면 됩니다.

lsmmay322 3년 전 0

앗 포문 하나로도 되나보군요..

나름 DP 사용한다고 했는데... 이중포문으로밖에 생각을 못했네요

저 코드도 나름 DP 맞긴 맞죠..?

전에 계산한걸 이용했으니

sr5757 3년 전 0

어떤 구간을 계산한 후, 그 값을 저장해서 재사용하면 포문 하나로 풀 수 있습니다!

이 코드에서는 전 단계에서 계산한 값(arr[i]를 포함하는 최대 연속합)을 재사용하지 못하고 있어 DP가 아닙니다.

anginjunddi 3년 전 0

-1 1 2라는 수열이 있을때

1에 -1을 더하는것 보다 더하지 않는게 더 크므로 그냥 1을 유지하고

2는 반대로 2를 유지하는것 보다 1을 더하는 것이 더 크기 때문에 1을 더해야 합니다.

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

문제

문제

출처

ICPC

1912 c언어 질문있습니다. 시간초과...

lsmmay322 3년 전 0

sr5757 3년 전 0

lsmmay322 3년 전 0

sr5757 3년 전 0

anginjunddi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말