글 읽기 - 97퍼에서 메모리초과

kdr06006 4년 전 0

퍼센트가 잘 올라가다가 메모리초과가 나오네요

배열크기(8백만)*int(4)하면 32MB라서 메모리 안 터질줄 알았는데 왜 터지는지 궁금합니다

#include<stdio.h>

const int _size = 4e6;
int N, M, arr[41], ans[_size * 2 + 1];
long long int cnt;

void BT(int idx, int sum)
{
	if (idx == (N + 1) / 2 + 1) {
		ans[sum + _size]++;
		return;
	}

	BT(idx + 1, sum);
	BT(idx + 1, sum + arr[idx]);
}

void _BT(int idx, int sum)
{
	if (idx == N) {
		cnt += ans[M - sum + _size];
		return;
	}

	_BT(idx + 1, sum);
	_BT(idx + 1, sum + arr[idx]);
}

int main(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) scanf("%d", &arr[i]);

	BT(0, 0);

	_BT((N + 1) / 2 + 1, 0);

	if (M == 0) cnt--;
	printf("%lld\n", cnt);
}

kdr06006 4년 전 1

N이 1일 때 무한루프돌아서 그렇군요

자체해결했습니다

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

문제

문제

출처

ICPC

97퍼에서 메모리초과

kdr06006 4년 전 0

kdr06006 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말