글 읽기 - 메모리 초과

njh7799 5년 전 0

시간 초과도 아니고 메모리 초과가 나던데, 어디 부분에서 초과가 났는지 짐작조차 안됩니다..ㅠ 혹 코드의 어디가 문제인지 알 수 있을까요

#include<cstdio>
#include<queue>
#define max(a,b) (((a)>(b))?(a):(b))
using namespace std;
bool d[9];
deque<int> dq1;
deque<char> dq2;
deque<int> number;
deque<char> cal;

int maxans = -1 << 20;

int calculator(int a, int b, char c) {
	if (c == '+') return a + b;
	if (c == '-') return a - b;
	if (c == '*') return a * b;
}

void go() {
	number = dq1;
	cal = dq2;
	// 괄호 먼저 처리
	int nsize = cal.size();
	number.push_back(number.front());
	number.pop_front();
	for (int i = 0; i < nsize; i++) {
		if (d[i]) {
			int dback = number.back();
			number.pop_back();
			number.push_back(calculator(dback, number.front(), cal.front()));
			number.pop_front();
			cal.pop_front();
		}
		else {
			number.push_back(number.front());
			cal.push_back(cal.front());
			number.pop_front();
			cal.pop_front();
		}
	}

	//괄호 계산 하고 남은 애들
	nsize = cal.size();
	int ans = number.front();
	number.pop_front();
	while (!number.empty()) {
		ans = calculator(ans, number.front(), cal.front());
		number.pop_front();
		cal.pop_front();
	}
	maxans = max(ans, maxans);
}

void dfs(int idx, int n) {
	if (idx == n - 1) {
		go();
		return;
	}
	dfs(idx + 1, n);
	if (d[idx] == 0) {
		d[idx + 1] = 1;
		dfs(idx + 1, n);
		d[idx + 1] = 0;
	}

}

int main() {
	int n;
	char st[20];

	scanf("%d", &n);
	scanf("%s", st);

	for (int i = 0; i < n; i++) {
		if (i % 2) dq2.push_back(st[i]);
		else dq1.push_back(st[i] - '0');
	}

	dfs(0, n/2);
	d[0] = true;
	dfs(0, n / 2);
	d[0] = false;

	printf("%d", maxans);
}

njh7799 5년 전 0

n이 1 일 경우에 dfs 함수에서 탈출 조건이 성립되지 못해 dfs가 무한히 생성되어 메모리 초과가 발생하였습니다.

ekfrhkquf12 4년 전 0

감사합니다ㅠㅠ 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

메모리 초과

njh7799 5년 전 0

njh7799 5년 전 0

ekfrhkquf12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말