글 읽기 - 메모리 초과가 왜 발생하는지 모르겠습니다.

solibaht 2년 전 0

vector를 사용하면 메모리 초과가 발생하지 않는데 array를 사용하면 메모리 초과가 발생합니다. ㅠㅡㅠ

32800이면 메모리를 그렇게 많이 잡아 먹는 것도 아니고 recursion에서 메모리 초과가 발생했다면 vector를 썼을 때도 문제가 있어야 할 거 같은데...

왜 이러는지 궁금해 미칠 거 같네요.

살려주세요...

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;

int N, C;
int w[30], g1[32800], g2[32800];
int ans = 0, p1 = 0, p2 = 0;

void dfs1(int s, int e, int sum) {
    if (s > e)
        g1[p1++] = sum;
    else {
        if (sum <= C)
            dfs1(s + 1, e, sum);
        if (sum + w[s] <= C)
            dfs1(s + 1, e, sum + w[s]);
    }
}

void dfs2(int s, int e, int sum) {
    if (s > e)
        g2[p2++] = sum;
    else {
        if (sum <= C)
            dfs2(s + 1, e, sum);
        if (sum + w[s] <= C)
            dfs2(s + 1, e, sum + w[s]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> C;
    for (int i = 0; i < N; i++)
        cin >> w[i];

    dfs1(0, N / 2, 0);
    dfs2(N / 2 + 1, N - 1, 0);
    sort(g1, g1 + p1);

    int st, ed, mid, c, t;
    for (int i = 0; i < p2; i++) {
        st = 0;
        ed = p1 - 1;
        c = C - g2[i];
        while (st <= ed) {
            mid = (st + ed) / 2;
            if (g1[mid] <= c) {
                st = mid + 1;
                t = mid;
            }
            else
                ed = mid - 1;
        }
        ans += t + 1;
    }
    cout << ans;
    return 0;
}

djm03178 2년 전 1

반으로 나누는 부분에 하자가 있습니다. N이 30이면 N/2는 15인데, [0,15]는 16개의 수이고 [16,29]는 14개의 수로 2개 차이가 납니다. 배열의 크기가 2^15까지만 수용할 수 있도록 만들어졌기 때문에 16개의 수를 완전탐색하면 도중에 배열의 크기를 넘어서게 되어 undefined behavior가 됩니다.

djm03178 2년 전 1

vector를 사용한 코드는 보지는 않았지만 아마도 push_back을 쓰셨기 때문에 불균일하게 나뉘더라도 시간상 손해가 있을 뿐 범위를 초과하는 문제는 없었을 거라고 추측합니다.

solibaht 2년 전 0

범위를 조금 조절했더니 해결됐네요!

정말 예리하시네요 :)

감사합니다.

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

문제

문제

출처

ICPC

메모리 초과가 왜 발생하는지 모르겠습니다.

solibaht 2년 전 0

djm03178 2년 전 1

djm03178 2년 전 1

solibaht 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말