글 읽기 - 시간초과 질문입니다!

peter1201 8년 전 0

분할정복밖에 생각이안나서 분할정복으로 짜봤는데요!

자꾸 시간초과가 뜨네요!

q1.혹시 제가 실수한부분이 있나요??!!

q2.다른방법으로 해야하나요??!!

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int arr[100001];
int maxV;
int solve(int s, int e)
{
	if (s == e)
		return arr[s];
	
	int minV = 987654321,mid,h;
	for (int i = s; i <= e; i++)
		if (arr[i] < minV)
		{
			minV = arr[i];
			mid = i;
		}
	
	if (mid == e)
		h = min(solve(s, mid - 1), arr[e]);
	else
		h = min(solve(s, mid), solve(mid + 1, e));
	maxV = max(maxV, h*(e - s + 1));
	return h;
}
int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		if (arr[i]>maxV)
			maxV = arr[i];
	}
	solve(0, n-1);
	cout << maxV;
	return 0;
}

hokma 8년 전 0

스택을 이용해서 O(n)으로 해결할 수 있는 방법이 있다고 합니다.

peter1201 8년 전 0

아 그렇군요 감사합니다.!

그런데 분할정복 시간복잡도가 nlogn인걸로 알고있는데요!

왜 시간초과가 나는지 궁금합니다!

peter1201 8년 전 0

아 정말 그렇네요 감사합니다!!

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

문제

문제

출처

ICPC

시간초과 질문입니다!

peter1201 8년 전 0

hokma 8년 전 0

peter1201 8년 전 0

peter1201 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말