글 읽기 - 메모리초과를 어떻게 처리해야할까요

alsgud3229 5년 전 0

큐에 너무많은 수가 들어가서 메모리가 터지는거 같은데 어떻게 줄일 수 있을까요?

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n,k;
queue<int> Q;
int t= 0;
bool visited[100005];
bool flag = false;

void BFS(){
    t++;
    int size = Q.size();

    while(size--){
        int front = Q.front();
        Q.pop();

        if(front+1<=100000) {
            for (int i = front + 1; i <= 100000; i = i * 2) {
                if(visited[i]==false){
                    visited[i]=true;
                    Q.push(i);
                }
                else{
                    break;
                }
                if(i==k){
                    flag = true;
                    return;
                }
            }
        }
        if(front-1>=0){
            for(int i=front-1; i<=100000; i=i*2){
                if(visited[i]==false){
                    visited[i]=true;
                    Q.push(i);
                }
                else{
                    break;
                }
                if(i==k){
                    flag = true;
                    return;
                }
            }
        }
    }
}

int main(){

    cin>>n>>k;
    for(int i=n; i<=100000; i=i*2){
        visited[i] = true;
        Q.push(i);
        if(i==k){
            cout<<t;
            return 0;
        }
    }

    while(!Q.empty()){
        BFS();
        if(flag){
            break;
        }
    }
    
    cout<<t;
   
    return 0;
}

redfowl 2년 전 0

이미 해결하셨을것 같지만 저도 메모리초과가 나서 고민했었는데

저는 처음에 N이 K보다 큰경우를 생각을 안했었더라구요.

그경우를 처리를 안해주면 큐가 엄청 커지더라구요 ㅠㅠ

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

문제

문제

출처

ICPC

메모리초과를 어떻게 처리해야할까요

alsgud3229 5년 전 0

redfowl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말