글 읽기 - 메모리 초과..

sambongdj 6년 전 0

자꾸 메모리 초과가 나네요..

분할정복으로 벡터에 속하는 좌표를 넣어서 인자로 줘서 그런걸까요...

다른 아이디어로 풀어야 할까요..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int maxN=0,minN=987654321;
int map[35000][2];

void solve(int y1,int x1,int y2,int x2,vector<int> v,int color){
    if(v.empty()){
        maxN = max(maxN,abs((y2-y1)*(x2-x1)));
        minN = min(minN,abs((y2-y1)*(x2-x1)));
        return;
    }
    int y=map[v[0]][0], x=map[v[0]][1];
    vector<int> nv1,nv2;
    if(color==0){
        for(int i=1;i<v.size();i++){
            if(map[v[i]][0]<y1&&map[v[i]][0]>y)
                nv1.push_back(v[i]);
            else nv2.push_back(v[i]);
        }
        solve(y1,x1,y,x2,nv1,1);
        solve(y,x1,y2,x2,nv2,1);
    }
    else {
        for(int i=1;i<v.size();i++){
            if(map[v[i]][1]>x1&&map[v[i]][1]<x)
                nv1.push_back(v[i]);
            else nv2.push_back(v[i]);
        }
        solve(y1,x1,y2,x,nv1,0);
        solve(y1,x,y2,x2,nv2,0);
    }
    return;
}

int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    vector<int > v;
    for(int i=0;i<k;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        map[i][0] = b;
        map[i][1] = a;
        v.push_back(i);
    }
    solve(m,0,0,n,v,0);
    cout << maxN << " " << minN << endl;
}

whquddn55 5년 전 0

4달 지난 글인데 아직 해결 못 하셨길래 남깁니다.

solve함수 인자로 vector를 통채로 copy해버려서 오버헤드가 너무 클 뿐만 아니라 그대로 copy하기때문에 메모리가 엄청 커집니다.

참조자로 참조해도 메모리초과가 뜰텐데 solve 재귀호출 직전에 v = vector<int>(); 로 vector capacity를 모두 비워줘야 초과가 안 뜹니다.

이 문제 풀면서 v.clear가 capacity는 그대로 남겨둔다는 걸 알았네요.

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

문제

문제

출처

ICPC

메모리 초과..

sambongdj 6년 전 0

whquddn55 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말