글 읽기 - 메모리 초과

thkighie1224 8년 전 0

부분 최대를 구하는 문제라서 Segment Tree로 접근하려고 했습니다.

배열로 먼저 데이터를 입력받고 Node에 데이터를 저장하는 방식으로 접근했는데

메모리 초과가 뜨네요 ㅜ.ㅜ

메모리 초과를 어떻게 해결해야 할지 감이 안잡히네요

처음부터 데이터를 넣어 줄때 마다 Segment Tree를 갱신해서 마지막 데이터를 넣었을때 Segment Tree도 완성되게 만들어야 하나요...?? ㅜ.ㅜ

#include<iostream>

using namespace std;

int min(int a, int b)
{
	if (a > b)		return b;
	else		return a;
}
int max(int a, int b)
{
	if (a > b)	return a;
	else
		return b;
}
struct Node
{
	struct Node* left;
	struct Node* right;
	int data;
};

struct Node* root;

int MakeTree(int* arr, int start, int end, struct Node* pnode)
{
	if (start == end)
		return pnode->data = arr[start];
	else
	{
		pnode->left = new struct Node;
		pnode->right = new struct Node;
	}
	
	int mid = (start + end) / 2;
	return pnode->data = min(MakeTree(arr, start, mid, pnode->left), 
		MakeTree(arr, mid + 1, end, pnode->right));
}

int Query(int start, int end, int startnode, int endnode, struct Node* pnode)
{
	int mid;
	start = max(start, startnode);
	end = min(end, endnode);
	if (start > end)
		return 987654321;
	if (start == startnode && end == endnode)
		return pnode->data;
	mid = (startnode + endnode) / 2;
	return min(Query(start, end, startnode, mid, pnode->left),
		Query(start, end, mid + 1, endnode, pnode->right));
}

int main(void)
{
	int N, M, val1, val2;
	int* arr;

	cin >> N >> M;
	arr = new int[N+1];
	root = new struct Node;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	for (int i = 0; i < M; i++)
	{
		MakeTree(arr, 1, N, root);
		cin >> val1 >> val2;
		cout << Query(val1, val2, 1, N, root) << endl;
	}
	return 0;
}

algoshipda 8년 전 0

아래와 같이 바꾸면 됩니다.

   
    for (int i = 0; i < M; i++)
    {
        MakeTree(arr, 1, N, root);
        cin >> val1 >> val2;
        cout << Query(val1, val2, 1, N, root) << endl;
    }
    
    ///////////////////////////////////////////////////
    MakeTree(arr, 1, N, root);   
    for (int i = 0; i < M; i++)
    {
        cin >> val1 >> val2;
        cout << Query(val1, val2, 1, N, root) << endl;
    }

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

문제

문제

출처

ICPC

메모리 초과

thkighie1224 8년 전 0

algoshipda 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말