글 읽기 - 메모리초과 -> 메모리계산법

skesswswkk 2년 전 0

메모리초과 에러가 나는 이유와

메모리계산하는 하는 방법이 궁금합니다!

추가로, 메모리초과 문제를 해결하면 아래 코드가 통과되는지 여부도 궁금합니다.

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

bool visited[3000 + 5];
vector<char> v;
vector<string> vv;
void sol(int cnt, int des, string s) {
	if (cnt == des) {
		string tmp = "";
		for (auto p : v) {
			tmp += p;
		}
		//cout << tmp << endl;
		vv.push_back(tmp);
		return;
	}

	for (int i = 0; i < des; ++i) {
		if (!visited[i]) {
			visited[i] = 1;
			v.push_back(s[i]);
			sol(cnt + 1, des, s);
			v.pop_back();
			visited[i] = 0;
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;

	string a, b;
	cin >> a >> b;

	//조합
	sol(0, n, a);

	int answer = 0;
	for (int i = 0; i < vv.size(); ++i) {
		if (b.find(vv[i]) != string::npos) {
			answer++;
		}
	}

	cout << answer << endl;
}

ehdrmsl2001 2년 전 0

최악의 경우 3000! 개의 순열이 벡터에 저장될 거 같은데 이 방법으로는 해결하기 어렵습니다.

또 재귀호출을 너무 많이 하는 것도 메모리 초과의 원인일 수 있습니다.

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

문제

문제

출처

ICPC

메모리초과 -> 메모리계산법

skesswswkk 2년 전 0

ehdrmsl2001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말