글 읽기 - 메모리 초과를 해결했는데 이유를 모르겠습니다...!

rlarlghks970113 3년 전 0

히스토그램 문제를 세그먼트 트리 방법을 이용해 풀었습니다

처음 문제를 풀었을 때는 메모리 초과가 떴는데요

함수에 쓰인 반환형들을 pair<int, int>에서 int로 바꿔주었더니 메모리 초과가 나지 않았습니다

구조도 똑같고 알고리즘도 똑같은데 int와 pair<>를 반환한다는 차이만으로 메모리초과가 날수 있는지 궁금합니다

#include <bits/stdc++.h>
#define INF 1000000000LL
using namespace std;

typedef long long ll;

int n;

// 노드 초기화
pair<int, int> init(vector<int>& arr, vector<pair<int,int>>& nodes, int left, int right, int node) {
    if(left == right) {
        nodes[node].first = arr[left];
        nodes[node].second = left;
        return nodes[node];
    }
    int mid = (left + right)/2;
    pair<int, int> leftMin = init(arr, nodes, left, mid, node*2);
    pair<int, int> rightMin = init(arr, nodes, mid+1, right, node*2 + 1);

    if(leftMin.first < rightMin.first) {
        nodes[node] = leftMin;
    } else {
        nodes[node] = rightMin;
    }

    return nodes[node];
}

// 쿼리
// 최솟값과 그에 해당하는 인덱스를 반환하자.
pair<int, int> queryMin(vector<pair<int, int>>& nodes, int left, int right, int node, int nodeLeft, int nodeRight) {
    // 겹치지 않을 때
    if(nodeRight < left || right < nodeLeft) return {INF, 0};
    // 완전 겹칠 때
    if(left <= nodeLeft && nodeRight <= right) return nodes[node];

    int mid = (nodeLeft + nodeRight) / 2;
    pair<int, int> leftMin = queryMin(nodes, left, right, node*2, nodeLeft, mid);
    pair<int, int> rightMin = queryMin(nodes, left, right, node*2 + 1, mid+1, nodeRight);

    pair<int, int> ret;
    if(leftMin.first < rightMin.first) {
        ret = leftMin;
    } else {
        ret = rightMin;
    }

    return ret;
}

// 함수 오버로딩
pair<int, int> queryMin(vector<pair<int, int>>& nodes, int left, int right) {
    return queryMin(nodes, left, right, 1, 1, n);
}

// 생각한 방법
// 분할정복법으로 풀자.
// 주어진 left ~ right 범위에서 높이가 가장 낮은 직사각형을 중심으로 셋으로 나누자.
// 나누어진 3개의 사각형 크기를 비교해서 가능한 최대 크기를 구해보자.
ll solve(vector<int>& arr, vector<pair<int,int>>& nodes, ll left, ll right) {
    // 기저사례 순서 주의
    // 기저사례 : 범위가 아예 사라졌을 때 사각형을 만들 수 없다.
    if(left > right) return 0;
    // 기저사례 : 더이상 쪼개질 수 없을 때 넓이를 반환하자.
    if(left == right) return arr[left];

    // left ~ right 범위에서 높이가 가장 낮은 사각형을 구하자.
    pair<int, int> minPair = queryMin(nodes, left, right);

    int pivot = minPair.second;
    ll leftMax = solve(arr, nodes, left, pivot-1);
    ll rightMax = solve(arr, nodes, pivot+1, right);
    ll tmpMax = (right - left + 1) * minPair.first;

    return max(leftMax, max(rightMax, tmpMax)); 
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    

    while(cin >> n)
    {
        if(n == 0) break;

        vector<int> arr(n+1);

        int h = (int)(ceil(log2(n))+1e-9);
        int tree_size = (1 << (h + 1));
        // first : 최솟값
        // second : 최솟값의 인덱스
        vector<pair<int, int>> nodes(tree_size);

        for(int i = 1; i <= n; ++i) cin >> arr[i];

        init(arr, nodes, 1, n, 1);

        cout << solve(arr, nodes, 1, n) << '\n';
    }
    return 0;
}

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

문제

문제

출처

ICPC

메모리 초과를 해결했는데 이유를 모르겠습니다...!

rlarlghks970113 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말