글 읽기 - 재귀 깊이 런타임에러?

rlarlvy153 6년 전 0

모든 집합 완전탑색 + 메모이제이션으로 구현해봤는데...

런타임에러를 발생시키네요 재귀 깊이인것 같습니다만, 최대 10000번 호출인데, 그것도 걸리나요?

잘 모르겠어서 질문납깁니다 ㅜㅜ

#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <cstdlib>
#include <functional>
#include <climits>
#include <sstream>
#include <map>
#include <set>


using namespace std;

int adj[10011][10011];
int dp[10011][10011];
int ans[10011];
vector<int> weight;
int n;
int dfs(int num, int depth) {
	if (depth == n) {
		return weight[num];
	}

	int &ret = dp[num][depth];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = num + 1; i <= n; i++) {
		if (adj[num][i] == 0) {
			if (ret < dfs(i, depth + 1)) {
				ret = dfs(i, depth + 1);
				ans[num] = i;
			}
		}
	}
	return ret = ret + weight[num];
}
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	cin >> n;
	int t;
	weight.push_back(0);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		cin >> t;
		weight.push_back(t);
	}
	int a, b;
	while (cin >> a >> b) {
		adj[a][b] = 1;
		adj[b][a] = 1;
	}
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		if (ret < dfs(i, 1)) {
			ans[0] = i;
			ret = dfs(i, 1);
		}
	}
	cout << ret << endl;
	int cur = ans[0];

	for (;;) {
		if (cur == 0 || cur > 10000) break;
		cout << cur << " ";
		cur = ans[cur];
	}
}

qja0950 6년 전 1

알고리즘 방법은 보지 않았습니다만,

10000 * 10000 * 2(두개) * 4(int) /1024 /1024 = 762.939453125 MB 로 메모리 초과인 것 같습니다.

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

문제

문제

출처

ICPC

재귀 깊이 런타임에러?

rlarlvy153 6년 전 0

qja0950 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말