글 읽기 - 고수님들 메모리초과 좀 잡아주세요ㅠ

projung0722 2년 전 0

동적할당을 사용해도 메모리초과가 나고 구글링해서 맞춘분의 답보고 적당한 크기로 선언해서 대략 500000 * 4 = 2000000 bite = 2000KB = 2MB 를 사용했다고 생각되는데 메모리초과가 납니다ㅠ 어디 부분을 수정해야할까요? 도와주십쇼 고수님들..

// 동적할당 코드
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
#define INF 1000000000

int init(int* arr, int* seg, int node, int s, int e);
int query(int* arr, int* seg, int node, int s, int e, int l, int r, int n);
void divideandconquer(int* arr, int* seg, int start, int end, int n);
ll maxarea;

int main()
{
	int n;
	while (1) {
		maxarea = 0;
		scanf("%d", &n);
		if (n == 0)
			break;
		int* arr;
		arr = (int*)malloc(sizeof(int) * (n+1));
		arr[n] = INF;
		int height = (int)ceil(log2(n));
		int node_cnt = 1 << (height + 1);
		int* seg;
		seg = (int*)malloc(sizeof(int) * (node_cnt));
		for (int i = 0; i < n; i++)
			scanf("%d", arr + i);
		init(arr, seg, 1, 0, n - 1);
		divideandconquer(arr, seg, 0, n - 1, n);
		printf("%lld\n", maxarea);
		free(seg);
		free(arr);
	}
	return 0;
}
int init(int* arr, int* seg, int node, int s, int e)
{
	if (s == e) return seg[node] = s;
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = init(arr, seg, 2 * node, s, mid);
	tmp2 = init(arr, seg, 2 * node + 1, mid + 1, e);
	if (arr[tmp1] < arr[tmp2])
		return seg[node] = tmp1;
	else
		return seg[node] = tmp2;
}
int query(int * arr,int* seg, int node, int s, int e, int l, int r, int n)
{
	if (e < l || r < s) return n;
	if (l <= s && e <= r) return seg[node];
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = query(arr, seg, 2 * node, s, mid, l, r, n);
	tmp2 = query(arr, seg, 2 * node + 1, mid + 1, e, l, r, n);
	if (arr[tmp1] < arr[tmp2])
		return tmp1;
	else
		return tmp2;
}
void divideandconquer(int* arr, int* seg, int start, int end, int n)
{
	int min;
	min = query(arr, seg, 1, 0, n - 1, start, end, n);
	if (maxarea < (ll)arr[min] * (end - start + 1))
		maxarea = (ll)arr[min] * (end - start + 1);
	if (start == end)
		return;
	if (min == start)
		divideandconquer(arr, seg, start + 1, end, n);
	else if (min == end)
		divideandconquer(arr, seg, start, end - 1, n);
	else {
		divideandconquer(arr, seg, start, min - 1, n);
		divideandconquer(arr, seg, min + 1, end, n);
	}
}

//전역변수 코드
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
#define INF 1000000000

int init(int node, int s, int e);
int query(int node, int s, int e, int l, int r, int n);
void divideandconquer(int start, int end, int n);
ll maxarea;
int arr[100001], seg[400001];

int main()
{
	int n;
	while (1) {
		maxarea = 0;
		scanf("%d", &n);
		if (n == 0)
			break;
		arr[n] = INF;
		for (int i = 0; i < n; i++)
			scanf("%d", arr + i);
		init(1, 0, n - 1);
		divideandconquer(0, n - 1, n);
		printf("%lld\n", maxarea);
	}
	return 0;
}
int init(int node, int s, int e)
{
	if (s == e) return seg[node] = s;
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = init(2 * node, s, mid);
	tmp2 = init(2 * node + 1, mid + 1, e);
	if (arr[tmp1] < arr[tmp2])
		return seg[node] = tmp1;
	else
		return seg[node] = tmp2;
}
int query(int node, int s, int e, int l, int r, int n)
{
	if (e < l || r < s) return n;
	if (l <= s && e <= r) return seg[node];
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = query(2 * node, s, mid, l, r, n);
	tmp2 = query(2 * node + 1, mid + 1, e, l, r, n);
	if (arr[tmp1] < arr[tmp2])
		return tmp1;
	else
		return tmp2;
}
void divideandconquer(int start, int end, int n)
{
	int min;
	min = query(1, 0, n - 1, start, end, n);
	if (maxarea < (ll)arr[min] * (end - start + 1))
		maxarea = (ll)arr[min] * (end - start + 1);
	if (start == end)
		return;
	if (min == start)
		divideandconquer( start + 1, end, n);
	else if (min == end)
		divideandconquer(start, end - 1, n);
	else {
		divideandconquer( start, min - 1, n);
		divideandconquer( min + 1, end, n);
	}
}

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

문제

문제

출처

ICPC

고수님들 메모리초과 좀 잡아주세요ㅠ

projung0722 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말