글 읽기 - 시간초과.. 도와주세요

kunwoo5012 4년 전 0

인터넷에 있는 블로그들을 참고하여 최소높이의 인덱스를 찾고, 그 인덱스를 기준으로 왼쪽, 오른쪽으로 다시 함수를 돌려 값을 찾는 방식으로 코드를 작성하였습니다. 하지만 계속해서 시간초과가 나네요.. 여러 질문들을 찾아봤는데, 도저히 모르겠어서 질문드립니다. 알려주시면 감사하겠습니다.

---------------------------------------------------------------------------

이후에 세그먼트 트리를 공부하고 이용해서 한번 짜봤는데.. 똑같이 시간초과가 나네요.

최솟값 인덱스 찾는 과정에서 시간이 많이 소모되는거 같은데, 도저히 모르겠습니다. 혹시, 이 글보시면 조금 도와주시면 감사하겠습니다.

코드는 수정한 코드로 바꾸었습니다.

#include <iostream>
#include <algorithm>

using namespace std;

//각 구간별 최소높이의 index를 저장한다
int init(int* arr, int* tree, int node, int start, int end)
{
	//리프노드일때
	if (start == end)
		return tree[node] = start;

	int mid = (start + end) / 2;
	int temp1_index = init(arr, tree, node * 2, start, mid);
	int temp2_index = init(arr, tree, node * 2 + 1, mid + 1, end);

	if (arr[temp1_index] > arr[temp2_index])
		return tree[node] = temp2_index;
	else
		return tree[node] = temp1_index;
}

//탐색 (최소높이의 인덱스를 반환)
int Serch_index(int * arr, int* tree, int node, int start, int end, int left, int right)
{
	//1.left, right 안에 start, end가 모두 포함될때
	if (left <= start && right >= end)
		return tree[node];
	//2. left, right 가 start, end와 아예 상관없을때
	else if (right < start || left > end)
	{
		return -1;	
	}
	//리프노드일때
	if (left == right)
		return left;
	//3. 약간 걸쳐 있을때
	int mid = (left + right) / 2;
	int a = Serch_index(arr, tree, node * 2, start, end, left, mid);
	int b = Serch_index(arr, tree, node * 2 + 1, start, end, mid+1, right);

	//a, b는 인덱스 값이므로 arr 값을 비교해서 최소높이로 결정
	// a나 b 가 -1이면 아예상관없는 값이므로 고려하기
	if (a == -1)
		return b;
	else if (b == -1)
		return a;
	
	// a, b가 다 유효한 값일때
	if (arr[a] >= arr[b])
		return b;
	else
		return a;
}

long long result;

void Solution(int * arr, int* tree, int node, int start, int end, int left, int right)
{
	if (left > right)
		return;
	//최소높이 찾기
	int temp = Serch_index(arr, tree, node, start, end, left, right);

	//넓이 넣기
	long long wid = right - left + 1;
	long long hei = arr[temp];
	result = max(result, wid * hei);

	if (left >= right)
		return;

	//분할

	//최소 높이를 기준으로 분할
	Solution(arr, tree, node, start, end, left, temp -1);
	Solution(arr, tree, node,  start, end,  temp +1, right);
}

int main(void)
{
	int n;
	while (1)
	{
		cin >> n;

		//탈출조건
		if (n == 0)
			break;

		int* arr = new int[n];
		int* tree = new int[4 * n];
		
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
		}

		init(arr, tree, 1, 0, n - 1);

		Solution(arr, tree, 1, 0, n-1, 0, n-1);

		cout << result << '\n';
		
		delete[] arr;
		delete[] tree;
	}
	

	return 0;
}

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

문제

문제

출처

ICPC

시간초과.. 도와주세요

kunwoo5012 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말