글 읽기 - 메모리 초과가 나는 이유를 알고 싶어요...

napnolem488 3년 전 0

예제를 대입해 보면 잘 나오는데, 왜 메모리 초과가 날까요? 코드 어디 부분이 잘못된 건지 알려주세요 ㅠ

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

int n, k, v[100], co=0, cnt=0,idx=0;
long long d[100001];
queue<pair<int, int> > q;
int main(){
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> co; 
        if(!d[co]){
            d[co]++; cnt++; v[idx++]=co; 
        } 
    }
    sort(v, v+cnt, greater<int>());
    int sum=0, num=0, ans;
    bool none=true;
    q.push({sum, num});
    while(1){
        if(q.empty()){  
            cout << -1<<'\n';
            none=false;
            break;
        }
        if(sum==k){
            ans = q.front().second;
            break;
        }
        for(int i=0; i<cnt; i++){
            if(sum+v[i]<=k) {    
                q.push({sum+v[i], num+1});
            }
        }
        q.pop();
        sum = q.front().first;
        num = q.front().second;
    }
    if(none){
        cout << ans <<'\n';
    }
}

ckdgus2482 3년 전 1

같은 sum인 노드가 큐에 중복으로 들어가는 것을 컷팅해야 합니다.

convert7342 3년 전 1

어차피 큐를 이용해서 풀이했으니 num이 작은 순서대로 queue에서 등장할겁니다.

따라서 큐에 push를 할 때 sum + v[i] 가 이미 등장했던 수라면 이 수는 큐에 넣을 필요가 없습니다.

위 코드에는@ckdgus2482 님이 말씀해주셨듯이 같은 sum인 노드가 큐에 중복으로 들어가기 때문에 메모리초과가 발생한 것입니다.

별도의 visit 배열을 만들어 중복방문을 체크해주도록하면 되겠습니다.

napnolem488 3년 전 0

아하 감사합니다! 해결했어요.

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

문제

문제

출처

ICPC

메모리 초과가 나는 이유를 알고 싶어요...

napnolem488 3년 전 0

ckdgus2482 3년 전 1

convert7342 3년 전 1

napnolem488 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말