글 읽기 - 이동하기 문제 메모리 초과

astrohsy 8년 전 0

1000 by 1000 배열 2개 있어도 256mb에는 훨 씬 못미치지는데..

어디서 메모리 초과가 발생하는지 모르겠어요...

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int map[1000][1000];
int res[1000][1000];


int main()
{
    int row, col;
    queue<pair<int,int>> q;
    
    cin >> row >> col;
    
    for(int i = 0; i<row; i++)
        for(int j = 0; j<col; j++)
            cin >> map[i][j];
    
    q.push( {0, 0} );
    res[0][0] = map[0][0];
    
    while( !q.empty() )
    {
        int x, y;
        x = q.front().first, y = q.front().second;
        q.pop();
        
        //아래로 이동
        if( x + 1 < row )
        {
            res[x+1][y] =  max( res[x+1][y], res[x][y] + map[x+1][y]);
            q.push({x+1, y});
        }
        
        if( y + 1 < col)
        {
            res[x][y+1] = max( res[x][y+1], res[x][y] + map[x][y+1]);
            q.push({x, y+1});
        }
    }
    
    cout<<res[row-1][col-1]<<endl;
}

kcm1700 8년 전 1

q가 커지네요.

ntopia 8년 전 1

kcm님의 댓글에 좀 더 부연설명을 드리자면,

같은 위치를 여러번 q에 집어넣고 있기 때문에

q의 크기가 거의 지수함수를 따라 커집니다.

그래서 이것 때문에 메모리 초과가 나는 것 같네요.

astrohsy 8년 전 0

감사합니다.. 그 부분 고쳐봐야 되겠네요.

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

문제

문제

출처

ICPC

이동하기 문제 메모리 초과

astrohsy 8년 전 0

kcm1700 8년 전 1

ntopia 8년 전 1

astrohsy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말